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

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

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

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,

$\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?

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

8. Ah, ok thanks