Looks impossible
Find the remainder when 1 0 3 0 is divided by 1 0 1 0 1 0 1 0 1 .
Details and assumptions
- 1 0 3 0 means 1 followed by thirty 0 s.
- The question is in base-10 or denary or decimal.
The answer is 1.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
Complete factorization for those of you that are interested: x 3 0 − 1 ≡ ≡ ≡ ≡ ≡ ( x 1 5 − 1 ) ( x 1 5 + 1 ) ( x 5 − 1 ) ( x 1 0 + x 5 + 1 ) ( x 5 + 1 ) ( x 1 0 − x 5 + 1 ) ( x 5 − 1 ) ( x 5 + 1 ) ( x 1 0 − x 5 + 1 ) ( x 1 0 + x 5 + 1 ) ( x − 1 ) ( x 4 + x 3 + x 2 + x + 1 ) ( x + 1 ) ( x 4 − x 3 + x 2 − x + 1 ) ( x 1 0 − x 5 + 1 ) ( x 1 0 + x 5 + 1 ) ( x − 1 ) ( x + 1 ) ( x 4 − x 3 + x 2 − x + 1 ) ( x 4 + x 3 + x 2 + x + 1 ) ( x 1 0 − x 5 + 1 ) ( x 1 0 + x 5 + 1 )
Log in to reply
I know the three line equal to symbol means modulus but how could you factorize the expression ( { (x }^{ 30 }-1) )\?
Log in to reply
Oh, I did not use the equivalent symbol in the sense of modulus here. The symbol here means that this is an identity, rather than an equation. For example, one could write x 2 = x + 8 which is an equation, rather than x 2 ≡ x + 8 which would be invalid.
And I factorized the expression x 3 0 − 1 using the difference of squares, difference of cubes, and difference of fifths.
In fact, x 2 − 1 ≡ ( x − 1 ) ( x + 1 ) , x 3 − 1 ≡ ( x − 1 ) ( x 2 + x + 1 ) , x 4 − 1 ≡ ( x − 1 ) ( x 3 + x 2 + x + 1 ) , x 5 − 1 ≡ ( x − 1 ) ( x 4 + x 3 + x 2 + x + 1 ) , x 6 − 1 ≡ ( x − 1 ) ( x 5 + x 4 + x 3 + x 2 + x + 1 ) , x 7 − 1 ≡ ( x − 1 ) ( x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 ) , and so on.
Bonus: can you prove that ( x − 1 ) is a factor of ( x k − 1 ) where k is a positive integer?
Log in to reply
@Kenny Lau – Thank you so much for the explanation. For your bonus question,
\[x\quad \equiv \quad 1\quad (mod\quad x-1)\quad \ \therefore \quad { x }^{ n }\equiv \quad { 1 }^{ n }\quad (mod\quad x-1)\ { x }^{ n }-1\quad \equiv \quad { 1 }^{ n }-1\quad (mod\quad x-1)\ { x }^{ n }-1\quad \equiv \quad 0\quad (mod\quad x-1)\ Similarly,\ x-1\quad \equiv \quad 0\quad (mod\quad x-1)\ \therefore \quad x-1|{ x }^{ n }-1\ Hence,\quad proved.]
or if the code doesn't display,
https://drive.google.com/file/d/0B42CxY5sovrLXzlyLTZ4RDM2cWc/view?usp=sharing
Thanks.
@Kenny Lau – By Remainder Theorem, ( x − 1 ) ∣ ( x k − 1 ) since if you plug in 1 the answer will be 0 for any positive integer k
Log in to reply
@Marc Vince Casimiro – Yep, that's what I had in mind :)
Here's a simple proof.
For every two digit number AB, note that 1 0 1 0 1 0 1 0 1 x AB is ABABABABAB.
Apply this nice property for 9 9 and we have
1 0 1 0 1 0 1 0 1 × 9 9 = 9 9 9 9 9 9 9 9 9 9
The remainder of 1 0 1 0 divided by 9 9 9 9 9 9 9 9 9 9 is simply their difference, namely 1 .
Hence also the remainder of 1 0 1 0 divided by 1 0 1 0 1 0 1 0 1 is still 1 .
Since 1 0 3 0 = ( 1 0 1 0 ) 3 , the remainder asked is 1 3 = 1 .
x 3 0 − 1 ≡ ≡ ( x 1 0 − 1 ) ( x 2 0 + x 1 0 + 1 ) ( x 2 − 1 ) ( x 8 + x 6 + x 4 + x 2 + 1 ) ( x 2 0 + x 1 0 + 1 )
Therefore ( x 8 + x 6 + x 4 + x 2 + 1 ) is a factor of x 3 0 − 1 .
Substitute x = 1 0 and we obtain the result that 1 0 1 0 1 0 1 0 1 is a factor of 1 0 3 0 − 1 . From that, we know that the required remainder is 1 .
Confirmed by WolframAlpha .