# Math Help - modulo arithmetic

1. ## maths help

..

2. Originally Posted by yellow4321
you have a calculator that can perform division with remainder 73 but cannot store nor output any number of size greater than +/-200, Show how to calculate 5^6 mod 73.

i know id use something like that (5^3)^2
$5^6 = (5^3)^2 = 125^2$

And
$125 \equiv 52~\text{mod 73}$

So
$5^6 = 125^2 \equiv 52^2~\text{mod 73}$

Now
$52 = 4 \cdot 13 = 2^2 \cdot 13$

Thus
$5^6 \equiv 52^2 = (2^2 \cdot 13) = 2^4 \cdot 13^2$

So finally:
$\equiv 16 \cdot 169 = 16 \cdot 23 = 8 \cdot 46 = 4 \cdot 92 \equiv 4 \cdot 19 = 76 \equiv 3~\text{mod 73}$

-Dan

3. Hello, yellow4321!

You have a calculator that can perform division with remainder 73
but cannot store nor output any number of size greater than $\pm200$
Show how to calculate: . $5^6 \pmod{73}$

Calculate successive powers of 5, reducing modulo 73.

$5^1 \;\equiv \;5 \pmod{73}$

$5^2\;\equiv\; 25 \pmod{73}$

$5^3 \;\equiv\;125 \;\equiv\;\text{-}21 \pmod{73}$

$5^4\;\equiv\;\text{-}105 \;\equiv\;\text{-}32 \pmod{73}$

$5^5 \;\equiv\;\text{-}160 \;\equiv\;\text{-}14 \pmod{73}$

$5^6 \;\equiv\;\text{-}70 \;\equiv\;3 \pmod{73}$

4. Originally Posted by Soroban
Hello, yellow4321!

Calculate successive powers of 5, reducing modulo 73.

$5^1 \;\equiv \;5 \pmod{73}$

$5^2\;\equiv\; 25 \pmod{73}$

$5^3 \;\equiv\;125 \;\equiv\;\text{-}21 \pmod{73}$

$5^4\;\equiv\;\text{-}105 \;\equiv\;\text{-}32 \pmod{73}$

$5^5 \;\equiv\;\text{-}160 \;\equiv\;\text{-}14 \pmod{73}$

$5^6 \;\equiv\;\text{-}70 \;\equiv\;3 \pmod{73}$

I suppose that's a lot easier than my convoluted method!

-Dan

5. much appreciated

6. Originally Posted by yellow4321
you have a calculator that can perform division with remainder 73 but cannot store nor output any number of size greater than +/-200, Show how to calculate 5^6 mod 73.

i know id use something like that (5^3)^2
By Fermat's Little Theorem,

$5^{72} \equiv 1 \pmod{73}$

But

$\underbrace{(5^6)(5^6)(5^6)...}_{12\ times}\equiv \underbrace{(3)(3)(3)...}_{12 \ times} \pmod{73}$

$\Rightarrow 5^{72} \equiv 36 \pmod{73}$

Is this correct? Why or why not?

7. Originally Posted by DivideBy0
By Fermat's Little Theorem,

$5^{72} \equiv 1 \pmod{73}$

But

$\underbrace{(5^6)(5^6)(5^6)...}_{12\ times}\equiv \underbrace{(3)(3)(3)...}_{12 \ times} \pmod{73}$

$\Rightarrow 5^{72} \equiv 36 \pmod{73}$

Is this correct? Why or why not?
Isnt $\underbrace{(3)(3)(3)...}_{12 \ times} = 3^{12}$??

8. Ah, ok thanks