Maths Olympiad Prep

Library / /102 of 133

Number theory Difficulty 6.3 National olympiad Prove it Saudi Arabia

Let p2p \geq 2 be a prime number and apbp=1+12++1p21\frac{a_{p}}{b_{p}} = 1 + \frac{1}{2} + \cdots + \frac{1}{p^{2}-1}, where apa_{p} and bpb_{p} are two relatively prime positive integers. Compute gcd(p,bp)\operatorname{gcd}\left(p, b_{p}\right).

Solution

For p=2p = 2 we have a2b2=116\frac{a_{2}}{b_{2}} = \frac{11}{6}, and therefore gcd(2,b2)=2\operatorname{gcd}\left(2, b_{2}\right) = 2.

For pp an odd prime we propose two solutions to this problem:

First solution. We have
apbp=k=1p21(p21)!k(p21)!. \frac{a_{p}}{b_{p}} = \frac{\sum_{k=1}^{p^{2}-1} \frac{(p^{2}-1)!}{k}}{(p^{2}-1)!} .
Because the only multiples of pp appearing in 1×2××(p21)1 \times 2 \times \cdots \times (p^{2}-1) are p,2p,,(p1)pp, 2p, \ldots, (p-1)p, and pp is a prime number, pp1p^{p-1} is the largest power of pp dividing (p21)!(p^{2}-1)!.
For 1kp211 \leq k \leq p^{2}-1, if kk is not a multiple of pp then pp1p^{p-1} divides (p21)!k\frac{(p^{2}-1)!}{k}. If kk is a multiple of pp then pp2p^{p-2} is the largest power of pp dividing (p21)!k\frac{(p^{2}-1)!}{k}.
Summing up the terms where kk is a multiple of pp we obtain
j=1p1(p21)!jp=(p21)!p!j=1p1(p1)!j \sum_{j=1}^{p-1} \frac{(p^{2}-1)!}{jp} = \frac{(p^{2}-1)!}{p!} \sum_{j=1}^{p-1} \frac{(p-1)!}{j}
Notice that all these fractions are integers. Using the fact that for each integer 1jp11 \leq j \leq p-1 there is a unique inverse integer 1ψ(j)p11 \leq \psi(j) \leq p-1 modulo pp (i.e. jψ(j)1modpj \psi(j) \equiv 1 \bmod p) and that this inverse map jψ(j)j \rightarrow \psi(j) is a permutation of {1,2,,p1}\{1,2, \ldots, p-1\}, we get
j=1p1(p1)!jj=1p1(p1)!jjψ(j)(p1)!j=1p1ψ(j)(p1)!j=1p1j(p1)!p(p1)20,(modp) \begin{aligned} \sum_{j=1}^{p-1} \frac{(p-1)!}{j} &\equiv \sum_{j=1}^{p-1} \frac{(p-1)!}{j} j \psi(j) \equiv (p-1)! \sum_{j=1}^{p-1} \psi(j) \\ &\equiv (p-1)! \sum_{j=1}^{p-1} j \equiv (p-1)! \frac{p(p-1)}{2} \equiv 0, \quad (\bmod p) \end{aligned}
This proves that pp1p^{p-1} divides j=1p1(p21)!jp\sum_{j=1}^{p-1} \frac{(p^{2}-1)!}{jp} and so it divides k=1p21(p21)!k\sum_{k=1}^{p^{2}-1} \frac{(p^{2}-1)!}{k}.
We deduce that pp1p^{p-1} cancels from the denominator and therefore
gcd(p,bp)=1. \operatorname{gcd}\left(p, b_{p}\right) = 1 .

Second solution. Because pp is odd, we have
apbp=k=1p212(1k+1p2k)=k=1p212p2k(p2k) \frac{a_{p}}{b_{p}} = \sum_{k=1}^{\frac{p^{2}-1}{2}} \left( \frac{1}{k} + \frac{1}{p^{2}-k} \right ) = \sum_{k=1}^{\frac{p^{2}-1}{2}} \frac{p^{2}}{k(p^{2}-k)}
For 1kp2121 \leq k \leq \frac{p^{2}-1}{2}, if kk is not a multiple of pp then the denominator k(p2k)k(p^{2}-k) is not divisible by pp. If kk is a multiple of pp then
p2k(p2k)=1j(pj), \frac{p^{2}}{k(p^{2}-k)} = \frac{1}{j(p-j)},
where k=jpk = jp for some integer 1jp121 \leq j \leq \frac{p-1}{2}. But the denominator j(pj)j(p-j) is not divisible by pp. Therefore apbp\frac{a_{p}}{b_{p}} is a sum of fractions where none of the denominators is divisible by pp and, since apbp\frac{a_{p}}{b_{p}} is irreducible, then gcd(p,bp)=1\operatorname{gcd}\left(p, b_{p}\right) = 1.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.