# modulo arithmetic

• Dec 31st 2007, 06:59 AM
yellow4321
maths help
..
• Dec 31st 2007, 07: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

$\displaystyle 5^6 = (5^3)^2 = 125^2$

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

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

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

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

So finally:
$\displaystyle \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, 07: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 $\displaystyle \pm200$
Show how to calculate: .$\displaystyle 5^6 \pmod{73}$

Calculate successive powers of 5, reducing modulo 73.

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

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

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

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

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

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

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

Originally Posted by Soroban
Hello, yellow4321!

Calculate successive powers of 5, reducing modulo 73.

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

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

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

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

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

$\displaystyle 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, 08:05 AM
yellow4321
much appreciated
• Dec 31st 2007, 09: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,

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

But

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

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

Is this correct? Why or why not?
• Dec 31st 2007, 09:24 AM
Isomorphism
Quote:

Originally Posted by DivideBy0
By Fermat's Little Theorem,

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

But

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

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

Is this correct? Why or why not?

Isnt $\displaystyle \underbrace{(3)(3)(3)...}_{12 \ times} = 3^{12}$??
• Dec 31st 2007, 09:52 AM
DivideBy0
(Tmi) Ah, ok thanks