What is the remainder of p| 12^(p-1), when p is prime?

I tried the division by the five first primes, but I don't see any partner in the remainder because for 2 and 3 the remainder is zero and for 5 and 7 is 1, but for 11 something to stay wrong, I don't know how to answer this question. Because tried prime by prime seems too wrong.

I know that I have to use this:

12^(p-1) = pk_{1} + r, but How??

1 Answer
Jun 11, 2018

The remainder is equal to 0 when p is either 2 or 3, and it is equal to 1 for all other prime numbers.

Explanation:

First of all this problem can be restated as having to find the value of 12^(p-1) mod p where p is a prime number.

To solve this problem you need to know Euler's Theorem. Euler's Theorem states that a^{\varphi(n)} -=1 mod n for any integers a and n that are coprime (They don't share any factors). You might be wondering what \varphi (n) is. This is actually a function known as the totient function. It is defined to be equal to the number of integers <=n such that those integers are coprime to n. Keep in mind that the number 1 is considered coprime to all integers.

Now that we know Euler's Theorem, we can go about solving this problem.

Note that all primes other than 2 and 3 are coprime with 12. Let's put aside 2 and 3 for later and focus on the rest of the primes. Since those other primes are coprime to 12, we can apply Euler's Theorem to them:

12^{\varphi (p)}-=1 mod p

Since p is a prime number, \varphi(p)=p-1. This makes sense because every number less than a prime number will be coprime with it.

Therefore, we now have 12^{p-1}-=1 mod p

The above expression can be translated to 12^{p-1} divided by p has a remainder of 1.

Now we just need to account for 2 and 3, which as you said earlier, both had remainders of 0.

Therefore, altogether we have proven that 12^{p-1} divided by p where p is a prime number has a remainder of 0 when p is either 2 or 3 and has a remainder of 1 otherwise.