Question

If p prime number, then prove
a^p = a mod p

Answer 1

@funinabox

Answer 2

yeah I looked at this before, but ran out of ideas lol

i'll think about it more

Answer 3

Ok

Answer 4

hi :) this is actually Fermat's Little Theorem. I suggest you do read up on it, and this is actually derived from Euler's Theorem.

We can start by listing the positive multiples of a:
a, 2a, 3a, ... (p -1)a

Suppose that r*a and s*a are the same modulo p, then we have r = s (mod p).

So the p-1 multiples of a above are distinct and not zero.

Thus, a*2a*3a.....(p-1)a = 1*2*3.....(p-1) (mod p)

We can simplify this into a(p-1)(p-1)! = (p-1)! (mod p).

Divide both sides by (p-1)! to complete the proof, and then we have a^p = a mod p :)

Have a nice day! Hope this helped :)

Answer 5

Sorry I couldn't type in the modulo sign, so I typed in the equal sign instead :)

Answer 6

i believe an additional step is required, because you proved a^(p-1) = 1mod p

you must multiply each side by a (assuming p is not a divisor of a)

Answer 7

then you'll have the more general formula a^p = a mod p

Answer 8

Thankyou