1. Consider the expression pp−1. We can factorize it as:
pp−1=(p−1)(pp−1+pp−2+⋯+p+1)
Notice that pp−1+pp−2+⋯+p+1 is a sum of p terms, each of which is greater than or equal to 1. Therefore, pp−1+pp−2+⋯+p+1>1.
2. Since pp−1+pp−2+⋯+p+1 is greater than 1, it must have a prime factor q. Thus, we have:
q∣pp−1+pp−2+⋯+p+1
and consequently,
q∣pp−1
This implies:
pp≡1(modq)
3. By definition, the order of p modulo q, denoted as ordq(p), is the smallest positive integer k such that:
pk≡1(modq)
Since pp≡1(modq), it follows that ordq(p) divides p. Given that p is a prime number, the possible values for ordq(p) are 1 or p.
4. If ordq(p)=1, then:
p≡1(modq)
Substituting p≡1(modq) into the sum pp−1+pp−2+⋯+p+1, we get:
1p−1+1p−2+⋯+1+1=p≡1(modq)
This implies:
q∣pp−1+pp−2+⋯+p+1
which contradicts the fact that q is a prime factor of pp−1+pp−2+⋯+p+1. Therefore, ordq(p)=1 is not possible.
5. Hence, we must have ordq(p)=p. Since ordq(p) divides q−1 (by Fermat's Little Theorem), it follows that:
p∣q−1
Therefore:
q≡1(modp)
6. Since q is a prime factor of pp−1 and q≡1(modp), we have shown that pp−1 has a prime factor that is congruent to 1 modulo p.
■