Consider $N=20132013 \ldots 2013$ , where $N$ consists of the number 2013 concatenated (repeated) 2013 times. What is the remainder of N when divided by 1001?
Details and assumptions
Concatenated: Combining 2 strings of numbers into one, by placing the first string directly before the second. For example, the number 123 concatenated 4 times would be 123123123123.
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.
Firstly notice that 2013/1001 and 20132013/1001 both leave a remainder other than zero. Secondly notice that 201320132013/1001 leaves a remainder of zero. Furthermore it is clear that every concatenation that is a multiple of 3 (e.g. 3,6,9...) divided by 1001 leaves a remainder of 0. Proceed to notice that 2013 is divisible by 3 (if the sum of the digits is divisible by 3, so is the number itself). Therefore the 2013th concatenation is a multiple 3, hence leaves a remainder of 0.
haha that's exactly how i did it :D Amazing right? U don't have to do it the long way :p
Same i did
$N = 2013 \cdot (10000^{2012} + 10^{2011} + \ldots + 10000 + 1)$
Note that $10000 \equiv -10 \pmod{1001}$ . So $10000^{6n + 1} \equiv -10 \pmod{1001}$ , $10000^{6n + 2} \equiv 100 \pmod{1001}$ , $10000^{6n + 3} \equiv -1 \pmod{1001}$ , $10000^{6n + 4} \equiv 10 \pmod{1001}$ , $10000^{6n + 5} \equiv -100 \pmod{1001}$ , $10000^{6n} \equiv 1 \pmod{1001}$ , where n is a non-negative integer.
$2012 = 6 \cdot 335 + 2$ . Hence $10000^{2012} + 10000^{2011} + \ldots + 10000 + 1$ $\equiv [100 + (-10) + 1 + (-100) + 10 + (-1)] \cdot 335 + 100 + (-10) + 1$ $\equiv 91 \pmod{1001}$ .
So $N \equiv 91 \cdot 2013 \equiv 91 \cdot 11 \equiv 1001 \equiv 0 \pmod {1001}$ .
For 2013 concatenated 3 times and divided by 1001, 201320132013/1001=201119013. Since 2013 is divisible by 3, 2013/3=671. N will be 201320132013 concatenated 671 times. Thus N/1001=0002111913 concatenated 671 times. So there will be no remainder and the answer is 0.
[Corrected several typos - Calvin]
Note that 201320132013/1001 is an integer. Therefore N=201320132013*(1+10^12+10^24+...+10^8048) is divisible by 1001.
First of all note that the number $201320132013$ is divisible by $1001$ . Then, we have $N = 201320132013 \times 10^{0 \times 12} + 201320132013 \times 10^{1 \times 12} + \cdots + 201320132013 \times 10^{671 \times 12}$ , which is obviously contain factors of $201320132013$ and thus, can be divided by $1001$ . Hence, the remainder is $0$
First, we note that $20132013...2013=2013 \times 100010001...10001$ , where the "1" is repeated 2013 times. There seems to be a suspicious relationship between the strings of 10001...10001 and 1001.
Denote the number 100010001....10001 (where there are k "1"s) by $k\$1$ . After placing the first few k's in mod 1001, we start to see the following pattern, which we will prove:
Claim: $3n\$1=91n (mod 1001)$ . Proof: We will show this through induction on n.
Base case: let $n=1$ . By long-division we can see that $3n\$1=100010001$ divided by 1001 leaves a remainder of $91=91 \times 1$ . Thus this case holds.
Inductive step: Assume it works for $n=k$ . We will show that it also works for $n=k+1$ .
From the assumption, we have that $3k\$1=91k (mod 1001)$ . Since $1000=-1(mod 1001)$ , it follows that $3k\$1 \times 1000^4=3k\$1 \times (-1)^4=3k\$1=91k (mod 1001)$ . We also know that $3\$1=91 (mod 1001)$ . Adding the two equations gives us $3k\$1 \times 1000^4 + 3\$1=(3k+3)\$1=3(k+1)\$1=91k+91=91(k+1) (mod 1001)$ , as desired. Thus the proof is complete.
Since $2013=3 \times 671$ , we know that $2013\$1=671*91=0 (mod 1001)$ . Hence N is also $0 (mod 1001)$ .
From N, we could subtract 200220022002...2002 (2013 times), to get 1100110011...0011 (0011 is repeated 2012 times after the leading 11). Note that 1100110011 is divisible by 1001.
Note that 11001100...11001100 (1100 is repeated 2013 times) is divisible by 1100110011, thus is divisible by 1001.
Thus, 11001100...110011 (0011 is repeated 2012 times after the leading 11) is just 1/100th of 11001100...11001100 (1100 is repeated 2013 times). Since it is still an integer, and 11001100...11001100 (1100 is repeated 2013 times) is divisible by 1001, 11001100...110011 (0011 is repeated 2012 times after the leading 11) is divisible by 2012.
200220022002...2002 (2013 times)+11001100...110011 (0011 is repeated 2012 times after the leading 11)=N. Since both of the addends is divisible by 1001, N is divisible by 1001, and the remainder is 0.
since 1001=7∗11∗13. So if the individual divisibility is ensured,is confirms for the compound. Because of the property of the primes.
Note: Here 7,11,13 are primes.
Property of the primes: If a prime p divides a number n and another prime q also divides the same number. Then the product pq also divides the number n.
Proof: since p divides n, n can be represented as n=p∗k. since q also divides n, then it is evident from the above that q divides k, as a result of the prime nature of p. so p∗q divides n.
Solution: 2013..........2013 has 4 ∗2013, even number of digits. checking the divisibility for 11: We consider the digit 201320132013, i.e 2013 repeating 3 times an odd number, since 2013 is also an odd number if proved for 3 it holds good for 2013 , after which it repeats and reoccurs. so 201320132013/11 is 18301830183 an integer, so 2013........2013 is divisible by 11, similarly 201320132013/13 is 15486164001, an integer ,extending to 7 201320132013/7 is 28760018859, an integer, so 2013.....2013 having 2013 repeating 2013 times in its decimal representation is divisible by 7,13,11 separately, because 201320132013 is, and here 2013 is repeating 3 times, since 3 and 2013 and odd, hence extensible. so 2013.....2013 is divisible by 7∗11∗13=1001. This completes our test.
Note that 2013=3x11x61 which is divisible by 3.
Note that 201320132013 is divisible by 1001.(which can be verified by long division.)
We'll prove by induction that 20132013...2013(3k 2013s) is divisible by 1001 for all k $\in \mathbb{N}$
The base case k=1 can be verified as above.
Inductive step:
20132013...2013(3k+3 2013s)
=201320132013( $10^{12k}$ ) + 20132013...2013(3k 2013s)
which is divisible by 1001 by the induction hypothesis.
The problem statement is just a special case when k=671.
Thus,the remainder is 0.
Observe that 1001(being symmetric) perfectly divides 201320132013(i.e. 2013 concatenated thrice)...now 2013 is divisible by 3. So 2013 concatenated 2013 times can be written as: A * 10^x + A * 10^(x-12) + ... [where A=201320132013 ] All of the parts are divisible by 1001...so the entire number is divisible by 1001...Remainder is 0.
201320132013 = 2013x(10 8+10 4+1) 2013 = 11 mod 1001 10 *4 = -10 mod 1001 201320132013 = 11 (-10X-10 + -10 +1) = 11*91 = 1001 = 0 mod1001 Since 2013 = 0 mod 3 (repeat 3 times) Hence N = 0 mod 1001
First of all, $\begin{aligned} 20132013\cdots2013&=201320132013\cdot 10^{8040}+201320132013\cdot 10^{8028}+\cdots+201320132013 \\ &=201320132013(10^{8040}+10^{8028}+\cdots+1) \end{aligned}$ Therefore, $201320132013|N$ .
Also, we find that $1001|201320132013$ , so $1001|N$ , making the answer $\boxed{0}$ .
Motivation: With this sort of problem with a large repeating block, you try to find a repeating portion that works and that can scale. Neither 2013 nor 20132013 works, but 201320132013 does.
The remainder we get from dividing a by b is defined as a mod b. Keeping this in mind,
2013201320132013201320132013mod1001=11 and so on...
So, from this, we can see, that the (3n+1)th concatenation gives us 11, (3n+2)th 902, and 3n gives us 0; where n is a positive integer.
You noticed that there is a cycle {11, 902, 0}, can you explain why this cycle occurs?
Log in to reply
No. I have 0 knowledge of Number Theory. I just find creative ways to solve problems. I'm looking forward to the Algebra format in practice section, for Number Theory. Can't wait to learn those concepts!
Notice that $1001|201320132013$ and $3|2013$ , so $N\equiv\boxed{0}\pmod{1001}$ .
We have following congruences modulo $1001$
$2013 = 1001 \times 2 + 11 \equiv 11$
$10^3 = 1000 \equiv -1$
$10^4 = 1001 \times 10 - 10 \equiv -10$
$N = 201320132013 .... 2013$ $= 2013 \times (000100010001 .... 0001 )$ $= 2013 \times (1 + 10^4 + (10^4)^2 + (10^4)^3 + ... + (10^4)^{2012} )$
$N \equiv 11 \times (1 - 10 + 10^2 - 10^3 + ... +10^{2012})$ $\equiv 11\times \frac{(-10)^{2013} - 1} {(-10) - 1 }$ $\equiv 10^{2013} + 1$ $\equiv (10^3)^{671} + 1$ $\equiv (-1)^{671} + 1$ $\equiv 0 \pmod{1001}$
So answer: $\boxed {0}$
Formula used: Sum of first n terms of a GP (Geometric Progression) is
$a + ar + ar^2 + ... ar^{n-1} = \frac {a.(r^n-1)}{r-1}$ for $r \neq 0, 1$
For 2013 concatenated 3 times and divided by 1001, 201320132013/1001=2111913 Since 2013 is divisible by 3, 2013/3=671 N will be 201320132013 concatenated 671 times Thus N/1001=2111913 concatenated 671 times So there will be no remainder and the answer is 0.
When 2013 is concatenated 3 times, the resulting number, 201320132013, is divisible by 1001. Thus, for every 3n, multiple of 3, concatenation, the resulting integer is a multiple of 1001. Since 2013 is a multiple of 3, 2013 concatenated 2013 times is a multiple of 1001. Thus the remainder is 0
Notice that 1000≡−1(mod1001). So powers of 10 repeat as follows 1, 10, 100, −1, −10, −100, 1, ⋯ which has period 6 so this allows us to remove lcm(6, 4)=12 digits, or three concatenated terms from the modulus and replace it with 201320132013≡0(mod1001) As 2013 is divisible by 3, this means that all terms will be eliminated, giving 2013(2013 times)≡0(mod1001)
As we know 0/2012 = 0 and it gives remainder of 0. When it contains one 2013 it gives remainder of 11,for two 2013 s it gives remainder of 902 and for three 2013 it gives remainder of 0 and this cycle continues.
The cycle is : 11,902,0,11,902,0,............................and so on As we can observe that for 3n number of 2013s the remainder is 0 where n = 0,1,2,3,4,5....... and as 2013 is divisible by 3 the remainder of 20132013.........2013 2013 times when divided by 1001 would be 0.
2013 modulus 1001 is 11, 20132013 modulus 1001 is 992 and 201320132013 modulus 101 is 0. therefore, the remainder is same every 3 step. 2013 modulus 3 is 0. therefore, the answer is same as 201320132013 modulus 1001, which is zero
$2013mod(1001)=11$
$20132013mod(1001)=902$
$201320132013mod(1001)=0$
$2013201320132013mod(1001)=11$
$20132013201320132013mod(1001)=902$
$201320132013201320132013mod(1001)=0$
As $2013mod(3)=0$ , so it has the same result with $201320132013mod(1001)=\boxed{0}$
Idem bro! Hahaha...
As N = 201320132013...2013 , 2013 concatenated 2013 times.
N = (201320132013)(201320132013)..(201320132013), let a = (201320132013) is 671 times and we can see that
a = (201320132013) is totally divisible by 1001.
Therefore, N is totally divisible by 1001. So, remainder is 0. (Ans)
I somewhat cheated for this problem. I used Python, a programming language, to do it for me. I had it make a string '2013'*2013, then converted it into an integer. Then, I used the remainder function (%) to find the answer.
We can notice that because 2013 repeats 201320132013......2013 = 2013 x 100010001000......1000.
We can work out that 100010001000.....1000 = 0 (mod 1001). Therefore 2013 x 0 (mod 1001) = 0 (mod 1001).
20132013.....2013 (where 2013 is concatenated 2013 times )
= 2013 ( 100010001...........10001)
= $2013 ( 1 + 10^4 + 10^8 + 10 ^{12} .........+ 10 ^{2013})$
therefore,
$2013 ( 1 + 10^4 + 10^8 +10 ^{12}....10^{2013}) \equiv 11( 1 +(-10) +100 + 1+ (-10) + 100 ......1+(-10)+100) \pmod {1001}$ $\equiv 11( 91 +91....+91)\pmod {1001}$ (where 91 occurs 671 times) $\equiv 11(91)(671)\pmod {1001}$ $\equiv 1001(671)\pmod {1001}$ $\equiv 0\pmod{1001}$
Therefore the remainder is 0
20132013.........................2013. Firstly,2013 leaves remainder 11 when divided by 1001. This will combine with the next no as 112013 . When divided by 1001 the remainder will be zero.Thus when the no of 2013's taken is divisible by 3,then the remainder is 0.In this question the no of 2013's taken is 2013 which is divisible by 3.Thus the remainder is zero.
Look 3 times 2013 That is 201320132013 is totally divisible by 1001 so Every Multiple of three times 2013 is divisible by 1001
Eg : 201320132013
201320132013201320132013
201320132013201320132013201320132013
And So On
Also 2013 is divisible by 3 so 2013 times 2013 is divisible by 1001
You Must Try This
Let x be an n-digit integer. I define f(x)=x 10^n+x. f(2013)=2013 10^4+2013. Now, 2013=4 (mod 7), 10^4=4(mod 7), therefore f(x)=4 4+4=6 (mod 7), and f^2(x)=0(mod 7), therefore f^2012(which is N)(x)=0(7). 2013=0(mod 11)=>f^2012(x)=N=0(mod 11). Do the same thing for 13 as we did for 7, and we get N=0(mod 13). 1001=7 11*13
Problem Loading...
Note Loading...
Set Loading...
Note that we can rewrite $N=2013(1+10^4+10^8+\cdots+10^{4\cdot 2012})$ So by the sum of a geometric series $N=2013(\frac{10^{4\cdot 2013}-1}{10^4-1})$ Note that $10^3\equiv -1\mod 1001$ , so $N\equiv 11(\frac{(-10)^{2013}-1}{-10-1})\equiv 10^{2013}+1\mod 1001$ But then $10^{2013}\equiv (10^3)^{671}\equiv -1\mod 1001$ So $N\equiv 0\mod 1001$ and we are done.