Problem: find 0 ≤ x ≤ 28 such that x^85 ≡ 6 modulo 35.
By Fermat-Euler theorem:
If a and n are coprime, i.e. (a,n)=1, then
a^phi(n) ≡ 1 mod n
where phi(n)=totient function, the number of positive integers less than n that is coprime with n.
for n=35, phi(35)=24 calculated as follows:
There are 10 positive integers from 1 to 34 which are NOT coprime with 35, namely {5,7,10,14,15,20,21,25,28,30}.Therefore phi(35)=34-10=24
From Fermat-Euler theorem,
x^(phi(35) = x^24 ≡ 1 modulo 35 since (24,35)=1, i.e. 24 and 35 are coprime.
=>
x^12 ≡ ± 1 modulo 35. ...........(1)
and
x^85 ≡ x^(85-3*24) ≡ x^(85-72) ≡ x^(13) ≡ 6 mod 35 ............(2)
Substituting (1) in (2)
x^(12)*x ≡ 6 mod 35
=>
(+1)*x = 6 mod 35 or (-1)*x ≡ 6 mod 35
x ≡ 6 mod 35 x ≡ -6 mod 35 (rejected)
=> x=6
So
6^85 ≡ 6 mod 35
If any clarifications are needed or if you find any errors, please post.
