A modulo 13 problem

[ayi]

Hi

I am having problem finding the remainder when 10^38 is divided by 13 i.e (10^38)mod13. Every time I calculate it myself I end up finding the answer 9 while matlab function 'rem(10^38,13)' always outputs 7.

For convenience I give my calculation here10^38)mod13=((13-3)^38)mod13=((-3)^38)mod13=((27)^12)*9 mod13=(1^12)*9 mod13=9

So, surely there something might have gone wrong.

Thanks in advance
-ayi

 

[Ishuda]

Hi

I am having problem finding the remainder when 10^38 is divided by 13 i.e (10^38)mod13. Every time I calculate it myself I end up finding the answer 9 while matlab function 'rem(10^38,13)' always outputs 7.

For convenience I give my calculation here10^38)mod13=((13-3)^38)mod13=((-3)^38)mod13=((27)^12)*9 mod13=(1^12)*9 mod13=9

So, surely there something might have gone wrong.

Thanks in advance
-ayi

Right idea so lets look at it
(a+b)ⁿ = \(\displaystyle \Sigma_{i=0}^{i=n}\) _nC_i \(\displaystyle a^{n-i} b^i = a \Sigma_{i=0}^{i=n-1}\) _nC_i \(\displaystyle a^{n-i-1} b^i\space \space +\space b^n\)
So with a = 13 and b = -3, we have (as you pointed out)
10³⁸ = 13 m₀ + (-3)³⁸ = 13 m₀ + 3³⁸

Let k = 3 i + j, j = 0, 1, 2
then,
3^k = 27ⁱ 3^j
= (2 * 13 + 1)ⁱ 3^j
or, in the same manner as above,
3^k = (2 * 13 m₁ + 1ⁱ) 3^j = 13 m₂ + 3^j

Now 38 = 3 * 12 + 2 so
3³⁸ = 13 m₂ + 3² = 13 m₂ + 9
and
10³⁸ = 13 m₀ + 13 m₂ + 9 = 13 m₃ + 9
and
10³⁸ = 9 mod (13)

Seems to me to be correct

Edit to add: When you start playing with moderately large number, the accuracy of calculators, whether full blown super computers or hand helds, is limited to the way numbers are stored and used. That is, round off error occurs. In matlab see what rem(10^38+6,13) gives you. If the true answer were 7 for your problem and matlab computed exactly, you should get an answer of 0.

 

[soroban]

Hello, Ayl!

I agree with your answer.

Find \(\displaystyle 10^{38}\text{ (mod 13)}\)

\(\displaystyle 10^{38} \;=\; (10^2)^{19} \;=\;(100)^{19}\)

. . . .\(\displaystyle \equiv\; (9)^{19} \text{ (mod 13)}\)

. . . .\(\displaystyle \equiv\;(9^3)^6\cdot 9\text{ (mod 13)}\)

. . . .\(\displaystyle \equiv\; (1)^6\cdot 9\text{ (mod 13)}\)

. . . .\(\displaystyle \equiv\; 9 \text{ (mod 13)}\)