# How to use Euler's theorem ?

• Apr 7th 2010, 07:57 AM
jjbrian
How to use Euler's theorem ?
Can someone please check/comment on my work?

1. Find the order of 7 modulo 172.
I did this by trial and error
7^1= 7(mod 172)
7^2= 49(mod 172)
7^3=171(mod 172) -----> 7^3 = -1(mod172)
squaring it
7^6 = (7^3)^2 = (-1)^2 = 1(mod 172)
so the order is 6

When I tried Euler method,
m =172
Φ(172) = Φ(2^2 * 43)
By rules: If p is prime then a) Φ(p)=p-1 b) Φ(p^e)=(p^(e-1))(p-1)
Φ(2^2 * 43) = 2*42 = 84
7^84= 1 (mod 172) [Can this be simplified?How?]

2. Prove that for any n, 33 divides (n^101) - n
33 has factors of 3 and 11. so n^101 - n is divisible by 11 and 3
I use fermat's theorem n^p = n (mod p)
n^p-1 = 1(mod p)

n= 1(mod 3)
n^100 = 1(mod 3)
n^100 * n= n(mod 3)
n^101 - n = 0 (mod 3)

n= 1(mod 11)
n^100 = 1(mod 11)
n^100 * n= n(mod 11)
n^101 - n = 0 (mod 11)
therefore n^101 - n divisible by 33.

Im not too sure if the proof is correct.
I would like to know how to do this problem with Euler's Theorem.

3. Calculate Φ(5525)
Φ(5525) = Φ(5^2 * 13 *17)
By rules: If p is prime then
a) Φ(p)=p-1 b) Φ(p^e)=(p^(e-1))(p-1)
Φ(5^2) = 20 Φ(13)=12 Φ(17)=16
Φ(5525) = 20*12*16 = 3840
• Apr 7th 2010, 09:04 AM
Amer
Quote:

Find the order of 7 modulo 172.
the order of a number "a" is the least number such a^r = 1 mod (certain number)

but in Euler's theorem they did not say $\displaystyle a^\phi(n)\equiv 1 (mod n)$ if (a,n)=1 but it is the not the least number

Example

$\displaystyle 5^2 \equiv 1 (mod 12)$

but $\displaystyle \phi(12) = (2^2 -2)(2) = 4$

$\displaystyle 5^3 \equiv 1 (mod 31)$

$\displaystyle \phi(31) = 30$

second question your proof is not correct since how do you know that

$\displaystyle n \equiv = 1 (mod 3)$
maybe n=5
but you can prove it like this
you have two cases for every case for 3

if 3 divide n it is clear that n^101-n is divisible by 3

if not (n,3)=1

$\displaystyle \phi(3) = 2$

$\displaystyle n^{100} = (n^2)^{50}$

$\displaystyle n^2 \equiv 1 (mod 3)$

$\displaystyle (n^2)^{50} =1 (mod 3)$ multiply with 3

$\displaystyle n^{101} = n (mod 3)$

for 11 same