Congruences, Fermats Little Theorm

[Nebula]

Can someone explain how to solve these types of things, my book gives one example and its useless:

find a such that 0 < a < 73
a=9^794(mod 73) (= means congruent equals)

solve
x^86=6(mod 29)

Thanks in advance :smile:

[robert Ihnot]

In the equation X^86 ==6 Mod 29, we note that for X not 0, X^28==1, by Fermat's Little Theorem. Thus X^86 ==X^28*X^28*X^28*X^2 ==X^2==6 Mod 29. That should be a start on the problem.

[Gokul43201]

For the first problem :

You could start from the ground up :

9^2 = 81== 8 (mod 73) => 9^4 == 64 == -9 => 9^8==81==8...(lucky!) and so on, but you don't have to, because 73 is prime and does not divide 9. So you can happily use the Little Theorem.

ie: 9^72 == 1 (mod 73) => (9^72)^n == 1^n = 1 (mod 73), for any n. With n=11, you get 9^792==1 (mod 73).

So 9^794 == 9^2 (mod 73)