Maths Olympiad Prep

Library / /64 of 520

Number theory Difficulty 6.4 National olympiad Prove it

Prove that if pp is a prime, then pp1p^{p}-1 has a prime factor that is congruent to 11 modulo pp.

Solution

1. Consider the expression pp1 p^p - 1 . We can factorize it as:
pp1=(p1)(pp1+pp2++p+1) p^p - 1 = (p-1)(p^{p-1} + p^{p-2} + \cdots + p + 1)
Notice that pp1+pp2++p+1 p^{p-1} + p^{p-2} + \cdots + p + 1 is a sum of p p terms, each of which is greater than or equal to 1. Therefore, pp1+pp2++p+1>1 p^{p-1} + p^{p-2} + \cdots + p + 1 > 1 .

2. Since pp1+pp2++p+1 p^{p-1} + p^{p-2} + \cdots + p + 1 is greater than 1, it must have a prime factor q q . Thus, we have:
qpp1+pp2++p+1 q \mid p^{p-1} + p^{p-2} + \cdots + p + 1
and consequently,
qpp1 q \mid p^p - 1
This implies:
pp1(modq) p^p \equiv 1 \pmod{q}

3. By definition, the order of p p modulo q q , denoted as ordq(p) \text{ord}_q(p) , is the smallest positive integer k k such that:
pk1(modq) p^k \equiv 1 \pmod{q}
Since pp1(modq) p^p \equiv 1 \pmod{q} , it follows that ordq(p) \text{ord}_q(p) divides p p . Given that p p is a prime number, the possible values for ordq(p) \text{ord}_q(p) are 1 or p p .

4. If ordq(p)=1 \text{ord}_q(p) = 1 , then:
p1(modq) p \equiv 1 \pmod{q}
Substituting p1(modq) p \equiv 1 \pmod{q} into the sum pp1+pp2++p+1 p^{p-1} + p^{p-2} + \cdots + p + 1 , we get:
1p1+1p2++1+1=p1(modq) 1^{p-1} + 1^{p-2} + \cdots + 1 + 1 = p \equiv 1 \pmod{q}
This implies:
qpp1+pp2++p+1 q \mid p^{p-1} + p^{p-2} + \cdots + p + 1
which contradicts the fact that q q is a prime factor of pp1+pp2++p+1 p^{p-1} + p^{p-2} + \cdots + p + 1 . Therefore, ordq(p)=1 \text{ord}_q(p) = 1 is not possible.

5. Hence, we must have ordq(p)=p \text{ord}_q(p) = p . Since ordq(p) \text{ord}_q(p) divides q1 q-1 (by Fermat's Little Theorem), it follows that:
pq1 p \mid q-1
Therefore:
q1(modp) q \equiv 1 \pmod{p}

6. Since q q is a prime factor of pp1 p^p - 1 and q1(modp) q \equiv 1 \pmod{p} , we have shown that pp1 p^p - 1 has a prime factor that is congruent to 1 modulo p p .

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.