Maths Olympiad Prep

Library / /31 of 520

Number theory Difficulty 6.3 National olympiad Find the answer

Determine all pairs (n,p)(n,p) of positive integers such that [list][*] pp is a prime, n>1n>1, [*] (p1)n+1(p-1)^{n} + 1 is divisible by np1n^{p-1}. [/list]

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

Solution

We need to determine all pairs (n,p)(n, p) of positive integers such that:
- pp is a prime,
- n>1n > 1,
- (p1)n+1(p-1)^n + 1 is divisible by np1n^{p-1}.

1. **Case: p=2p = 2**

If p=2p = 2, then we need n1n+1=2n \mid 1^n + 1 = 2. Since n>1n > 1, the only possible value for nn is n=2n = 2. Therefore, (n,p)=(2,2)(n, p) = (2, 2) is a solution.

2. **Case: pp is odd**

Let qq be the smallest prime divisor of nn and let oo be the order of p1modqp-1 \mod q. Since (p1)2n1modq(p-1)^{2n} \equiv 1 \mod q, we get o2no \mid 2n. By Fermat's Little Theorem, oq1o \mid q-1.

If oo has a factor in common with nn, this factor would be q1<q\leq q-1 < q, which is impossible. Therefore, o2no \mid 2n reduces to o2o \mid 2, yielding (p1)21modq(p-1)^2 \equiv 1 \mod q or equivalently qp(p2)q \mid p(p-2).

- **Subcase: qp2q \mid p-2**

We get (p1)n+11n+1=2modq(p-1)^n + 1 \equiv 1^n + 1 = 2 \mod q. But we need qq to divide this number, thus q=2q = 2. However, this implies pp is even, so p=2p = 2, which we excluded in this case.

- **Subcase: qpq \mid p**

We write n=pksn = p^k s where psp \nmid s and k>0k > 0. It is well known that for odd primes pp, if vp(ab)>0v_p(a - b) > 0 and pa,bp \nmid a, b, then vp(atbt)=vp(ab)+vp(t)v_p(a^t - b^t) = v_p(a - b) + v_p(t) (where vp(m)v_p(m) is the pp-adic valuation of mm, the number of times mm is divisible by pp). With a=p1a = p-1, b=1b = -1, and t=nt = n, this gives us vp((p1)n+1)=k+1v_p((p-1)^n + 1) = k + 1 and it has to be k(p1)\geq k(p-1) to enable pk(p1)np1(p1)pks+1p^{k(p-1)} \mid n^{p-1} \mid (p-1)^{p^k s} + 1. Now k+1k(p1)    2k+1kp    2+1kpk + 1 \geq k(p-1) \iff 2k + 1 \geq kp \iff 2 + \frac{1}{k} \geq p. Since we assumed p3p \geq 3, we have k=1k = 1 and p=3p = 3.

If s=1s = 1, we have n=3n = 3 giving a solution. So let's assume s>1s > 1. Let qq be the smallest prime divisor of ss. By n=3n = 3, we want s9s2=n22n+1=8s+1s \mid 9s^2 = n^2 \mid 2^n + 1 = 8^s + 1. Following the same idea as before, we take oo as the order of 8modq8 \mod q and get again o2o \mid 2 by the same argument. In both cases, q821=63q \mid 8^2 - 1 = 63, thus q=7q = 7. But 8s+11s+1=2mod78^s + 1 \equiv 1^s + 1 = 2 \mod 7, which is a contradiction.

Conclusion: All solutions are given by (n,p)=(2,2),(3,3)(n, p) = (2, 2), (3, 3).

The final answer is (2,2),(3,3) \boxed{ (2, 2), (3, 3) } .

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.