1
$\begingroup$

Let $\mathbb{Z}_p^*$, where $p$ is prime and let $a\in\mathbb{Z}_p^*$.

Consider the following equation:$$(p-1)! \equiv (p-1)! a^{p-1} \mod p$$

I've read that since $\gcd((p-1)!, p) = 1$ we can infer that $$a^{p-1} \equiv 1$$

So I have two questions:

  1. Why is it true that $\gcd ((p-1)!, p)= 1$?
  2. Why can we infer that $a^{p-1} \equiv 1$?
|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ for the frist question: if $p$ is prime then observe than $(p-1)!$ doesnt contain $p$ as a factor, hence $\gcd((p-1)!,p)=1$ $\endgroup$ – Masacroso Mar 19 '17 at 15:44
  • $\begingroup$ And for the second question, you can always write the $gcd(a,b)$ as a linear combination of $a$ and $b$ with integer coefficients (this is from the Euclidean algorithm). Use this to show that if some number is relatively prime to $p$, then it has a multiplicative inverse mod $p$. $\endgroup$ – Malkoun Mar 19 '17 at 15:46
  • $\begingroup$ Fermat's little theorem en.wikipedia.org/wiki/Fermat%27s_little_theorem?wprov=sfla1 $\endgroup$ – Zuo Mar 19 '17 at 15:51
0
$\begingroup$

  1. The only divisors of $p$ are $p$ and $1$. What are the divisors of $(p-1)!$?

  2. Once you know that $p, (p-1)!$ are relatively prime, consider $(p-1)! * (a^{p-1} - 1) \equiv 0 \mod p$. The relative primeness tells you that this is only possible if $(a^{p-1} - 1) \equiv 0 \mod p$

|cite|improve this answer
$\endgroup$
3
$\begingroup$

This common result is known as Fermat's Little Theorem. I hope this simple proof helps:

Consider the sequence of integers $n,2n,3n,…,(p−1)n$.

Note that none of these integers are congruent modulo $p$ to the others.

If this were the case, we would have $an≡bn \pmod p$ for some $1≤a<b≤p−1$.

Then as $gcd(n,p)=1$, and we can cancel the $n$, we get $a≡b \pmod p$ and so $a=b$.

Also, since $p∤n$ and $p∤c$, for any $1≤c≤p−1$, then by Euclid's Lemma $p∤cn$ for any such $cn$, which means $cn≢0 \pmod p$.

Thus, each integer in the sequence can be reduced $modulo \ p$ to exactly one of $1,2,3,…,p−1$.

So ${1,2,3,…,p−1}$ is the set of Reduced Residue System $modulo \ p$.

So, upon taking the product of these congruences, we see that $n×2n×3n×⋯×(p−1)n≡1×2×3×⋯×(p−1) \mod p$.

This simplifies to $n^{p−1}×(p−1)!≡(p−1)! \pmod p$.

Since $p∤(p−1)!$, we can cancel $(p−1)!$ from both sides, leaving us with $n^{p−1}≡1 \pmod p$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The last statement is essentially my question. Why does the fact $p\not\vert (p-1)!$ implies that you can cancel $(p-1)!$ from both sides? $\endgroup$ – OliOliver Mar 19 '17 at 16:14
  • 1
    $\begingroup$ It doesn't essentially imply that $(p-1)!$ is being cancelled because of that property. It merely states that they are relatively prime to each other and, hence, we can use the property of modular arithmetic to basically remove $(p-1)!$ as if it of no use here(as we are dealing with, say, modulo $p$ and not modulo $(p-1)!$) and appears on both sides leaving it to be factored out. $\endgroup$ – HKT Mar 19 '17 at 16:25
  • 1
    $\begingroup$ Carefully think about it. Suppose if $p|(p-1)!$, we would have been left with $0 \pmod p$ on the right hand side. I hope that helps. $\endgroup$ – HKT Mar 19 '17 at 16:28
  • 1
    $\begingroup$ You are just over-thinking it. I assure you once you get the hang of it and review the basic modular arithmetic definitions and get a stronger grasp on the notation, there will be clarity. $\endgroup$ – HKT Mar 19 '17 at 16:30
2
$\begingroup$

If you write down $(p-1)!$ as $(p-1)\cdot(p-2)\cdot\cdot\cdot1$ you can easily notice that $p$ and $(p-1)!$ have no common factors.

So $gcd((p-1)!,p) = 1$.

Now, knowing that:

$$ax \equiv b \mod(m) \implies x \equiv b \cdot a^{-1} \mod(\frac{m}{gcd(m,a)})$$

you have the answer to your question.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ You might as well just write $ax\equiv b\bmod m\implies x=a^{-1}b\bmod m$ when $\gcd(a,m)=1$. No need to overcomplicate it. $\endgroup$ – arctic tern Mar 19 '17 at 15:55
0
$\begingroup$

For the first question, take, for example, $p = 7$. Then $(p-1)! = 2\cdot3\cdot4\cdot5\cdot6 = 2^4\cdot3^2\cdot5$. Notice that in the first equation all of the factors are strictly less than $p = 7$, which implies that all of the prime factors are also strictly less than $p$. Since $p$ is prime, this means that $p$ and $(p-1)!$ can have no prime factors in common.

Now this implies Fermat's little theorem because, having shown that $(p-1)!$ is relatively prime with $p$, we can apply the cancellation law.

Whenver $\gcd(a,m) = 1$, $$ax \equiv ay \mod m$$ $$\downarrow$$ $$x \equiv y \mod m$$

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.