Question

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??

Answer 1

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.