# modulo arithmetic

• Dec 31st 2007, 07:59 AM
yellow4321
maths help
..
• Dec 31st 2007, 08:12 AM
topsquark
Quote:

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
• Dec 31st 2007, 08:18 AM
Soroban
Hello, yellow4321!

Quote:

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}$

• Dec 31st 2007, 08:43 AM
topsquark
Quote:

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}$

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

-Dan
• Dec 31st 2007, 09:05 AM
yellow4321
much appreciated
• Dec 31st 2007, 10:17 AM
DivideBy0
Quote:

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?
• Dec 31st 2007, 10:24 AM
Isomorphism
Quote:

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}$??
• Dec 31st 2007, 10:52 AM
DivideBy0
(Tmi) Ah, ok thanks