Maths Olympiad Prep

Library / /115 of 520

Number theory Difficulty 5.8 AIME, harder Find the answer

Find all positive integers nn such that there exists a prime number pp, such that

pn(p1)n p^{n}-(p-1)^{n}

is a power of 3.

Note. A power of 3 is a number of the form 3a3^{a} where aa is a positive integer.

A number or a short expression. Spacing and $ signs are ignored.

Solutions — 2

Solution 1

Suppose that the positive integer nn is such that

pn(p1)n=3a p^{n}-(p-1)^{n}=3^{a}

for some prime pp and positive integer aa.

If p=2p=2, then 2n1=3a2^{n}-1=3^{a} by (1)(1), whence (1)n10(mod3)(-1)^{n}-1 \equiv 0(\bmod 3), so nn should be even. Setting n=2sn=2 s we obtain (2s1)(2s+1)=3a\left(2^{s}-1\right)\left(2^{s}+1\right)=3^{a}. It follows that 2s12^{s}-1 and 2s+12^{s}+1 are both powers of 3, but since they are both odd, they are co-prime, and we have 2s1=12^{s}-1=1, i.e. s=1s=1 and n=2n=2. If p=3p=3, then (1) gives 32n3 \mid 2^{n}, which is impossible.

Let p5p \geq 5. Then it follows from (1) that we can not have 3p13 \mid p-1. This means that 2n102^{n}-1 \equiv 0 (mod3)(\bmod 3), so nn should be even, and let n=2kn=2 k. Then

p2k(p1)2k=3a(pk(p1)k)(pk+(p1)k)=3a p^{2 k}-(p-1)^{2 k}=3^{a} \Longleftrightarrow\left(p^{k}-(p-1)^{k}\right)\left(p^{k}+(p-1)^{k}\right)=3^{a}

If d=(pk(p1)k,pk+(p1)k)d=\left(p^{k}-(p-1)^{k}, p^{k}+(p-1)^{k}\right), then d2pkd \mid 2 p^{k}. However, both numbers are powers of 3, so d=1d=1 and pk(p1)k=1,pk+(p1)k=3ap^{k}-(p-1)^{k}=1, p^{k}+(p-1)^{k}=3^{a}.

If k=1k=1, then n=2n=2 and we can take p=5p=5. For k2k \geq 2 we have 1=pk(p1)kp2(p1)21=p^{k}-(p-1)^{k} \geq p^{2}-(p-1)^{2} (this inequality is equivalent to p2(pk21)(p1)2((p1)k21)p^{2}\left(p^{k-2}-1\right) \geq(p-1)^{2}\left((p-1)^{k-2}-1\right), which is obviously true). Then 1p2(p1)2=2p191 \geq p^{2}-(p-1)^{2}=2 p-1 \geq 9, which is absurd.

It follows that the only solution is n=2n=2.

Solution 2

To solve the problem, we need to find all positive integers n n such that there exists a prime number p p for which pn(p1)n p^n - (p-1)^n is a power of 3. Let's go through the solution step-by-step.

1. Initial Considerations:
- We are given that pn(p1)n p^n - (p-1)^n is a power of 3, i.e., pn(p1)n=3a p^n - (p-1)^n = 3^a for some positive integer a a .
- Since 30=1 3^0 = 1 is not considered a power of 3, we have n>1 n > 1 .

2. Modulo 3 Analysis:
- Consider the expression modulo 3. If p0(mod3) p \equiv 0 \pmod{3} , then p p is divisible by 3, which is not possible since p p is a prime number.
- If p1(mod3) p \equiv 1 \pmod{3} , then p10(mod3) p-1 \equiv 0 \pmod{3} , making (p1)n0(mod3) (p-1)^n \equiv 0 \pmod{3} . Thus, pn3a(mod3) p^n \equiv 3^a \pmod{3} , which is not possible since pn1(mod3) p^n \equiv 1 \pmod{3} and 3a0(mod3) 3^a \equiv 0 \pmod{3} .
- Therefore, p2(mod3) p \equiv 2 \pmod{3} .

3. Simplifying the Expression:
- Given p2(mod3) p \equiv 2 \pmod{3} , we have p11(mod3) p-1 \equiv 1 \pmod{3} .
- Thus, pn2n(mod3) p^n \equiv 2^n \pmod{3} and (p1)n1n1(mod3) (p-1)^n \equiv 1^n \equiv 1 \pmod{3} .
- Therefore, pn(p1)n2n10(mod3) p^n - (p-1)^n \equiv 2^n - 1 \equiv 0 \pmod{3} , which implies 2n1(mod3) 2^n \equiv 1 \pmod{3} .

4. **Determining n n :**
- The congruence 2n1(mod3) 2^n \equiv 1 \pmod{3} holds if and only if n n is even. Let n=2k n = 2k .

5. **Further Analysis for n=2k n = 2k :**
- Consider n=4m n = 4m (i.e., n n is a multiple of 4). We have:
p4(p1)4=(p2(p1)2)(p2+(p1)2) p^4 - (p-1)^4 = (p^2 - (p-1)^2)(p^2 + (p-1)^2)
- Simplifying, we get:
p2(p1)2=p2(p22p+1)=2p1 p^2 - (p-1)^2 = p^2 - (p^2 - 2p + 1) = 2p - 1
p2+(p1)2=p2+(p22p+1)=2p22p+1 p^2 + (p-1)^2 = p^2 + (p^2 - 2p + 1) = 2p^2 - 2p + 1
- Since p2(mod3) p \equiv 2 \pmod{3} , we have:
p241(mod3)and(p1)21(mod3) p^2 \equiv 4 \equiv 1 \pmod{3} \quad \text{and} \quad (p-1)^2 \equiv 1 \pmod{3}
- Thus, p2+(p1)21+12(mod3) p^2 + (p-1)^2 \equiv 1 + 1 \equiv 2 \pmod{3} , which cannot be a power of 3.

6. **Conclusion for n=2k n = 2k :**
- Since n=4m n = 4m is not possible, we must have n=2k n = 2k where k k is odd.
- If k>1 k > 1 , then pk(p1)k p^k - (p-1)^k must also be a power of 3, which is not possible by our previous analysis.
- Therefore, k=1 k = 1 , and n=2 n = 2 .

7. Verification:
- For n=2 n = 2 , we have:
p2(p1)2=p2(p22p+1)=2p1 p^2 - (p-1)^2 = p^2 - (p^2 - 2p + 1) = 2p - 1
- We need 2p1=3a 2p - 1 = 3^a . For a=1 a = 1 , we get 2p1=3    2p=4    p=2 2p - 1 = 3 \implies 2p = 4 \implies p = 2 , which is a prime number.
- For p=2 p = 2 , we have 2212=41=3=31 2^2 - 1^2 = 4 - 1 = 3 = 3^1 , which is indeed a power of 3.

Thus, the only solution is n=2 n = 2 .

The final answer is n=2 \boxed{n = 2} .

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.