Question

121212 ... 121 (mod 121) = ?
Number of digits in the number - 67.
Need someone to verify my answer.

Answer 1

I got an answer of 12. Is it right?

Answer 2

\[\large \underbrace{121212\ldots 121}_{\text{number of digits = 67}} \pmod {121} = \ ? \]

Answer 3

I solved it in a way that is described there: http://www.devx.com/tips/Tip/39012

Answer 4

What did you get?

Answer 5

12. Is it right?

Answer 6

No, numerically not even close.
I have not gone through the method.
Would you be kind enough to show the calculations according to the method, so we can all learn from you together?

Answer 7

is this supposed to be a programming or math question ?

Answer 8

Math. The way works perfectly with just human brain.

Answer 9

= below will be to show that it's congruent

121 = 0 (mod 121)
Let's subtract 12100...000 (64 zeros) and take mod of it, it will be equal to 0. Let's continue with that. We get a number like this:
200020002000...2000 (64 digits)
2000 = 64 (mod 121)
We get a number 64646464...64 (32 digits)
with similar method we do that to get congruency to 51, 69, 72 and then 12.

Answer 10

I was interested, if it would really work. That's why I asked the question. ;)

Answer 11

This looks like a mix of chinese remainder theorem and some other stuff

Answer 12

Well, I have no idea about Chinese remainder theorem, will take a look into it later. Would anyone confirm if my answer might be true? If it's not, please tell me the right answer :)

Answer 13

Suppose you need to find n (mod a) and n is very big number:

Take a manageable portion (say, x) of the input large number (n) and subtract it from n (n = n - x).

Compute the mod of x (x (mod a)).

Add the mod to n (n = n + x (mod a)). This way, the number n can be reduced without affecting the actual answer.

Answer 14

Is it right?

Answer 15

200020002000...2000 (64 digits)
2000 = 64 (mod 121)
We get a number \(\color{red}{64646464...64 (32 digits) }\)
it would be actually
"0064006400640064006400640064006400640064006400640064006400640064", 64 digits.
Up to here it still works. The mod is still 89.

Answer 16

Thank you!

Answer 17

Yes, the methods sounds interesting, and it remains a good tool!
Thank you for sharing! :)

Answer 18

Post-script:
According to the method, you only have to iterate 16 times x=mod(x*10000+0064,121), as follows:
[x:0],for i:1 thru 16 do (x:mod(x*10000+64,121),print(x));
64
95
93
58
111
10
118
72
114
2
99
42
73
71
36
89 (mod of original number)

This method allows finding mod of large numbers in small chunks to fit in the limited memory of most binary calculators. But your application is very relevant, because it is then a simple iteration, as shown above.

Answer 19

Thank you for showing this to me, @mathmate !

Answer 20

You're welcome! :)
I did so because I found that the method actually works, and would like to share with everyone!