Maths Olympiad Prep

Library / /454 of 520

Number theory Difficulty 7.0 National olympiad Prove it

Example 1 Let uu be a given positive integer, prove that the equation
n!=uxuyn!=u^{x}-u^{y}

has at most finitely many positive integer solutions (n,x,y)(n, x, y).

Solution

Prove that we can assume u>1u>1. The conclusion is equivalent to proving that the equation
n!=ur(us1)n!=u^{r}\left(u^{s}-1\right)

has at most finitely many positive integer solutions (n,r,s)(n, r, s).
First, note that for a given nn, equation (1) clearly has at most finitely many solutions (r,s)(r, s). We will prove that when nn is sufficiently large, equation (1) has no solutions, which will prove the above conclusion.

Choose a prime pup \nmid u. We can assume (1) has a solution n>pn>p (otherwise, there is nothing to prove), and let pαn!p^{\alpha} \| n!, then
α=l=1[npl][np]>an,\alpha=\sum_{l=1}^{\infty}\left[\frac{n}{p^{l}}\right] \geqslant\left[\frac{n}{p}\right]>a n,

where aa is a (positive) constant that depends only on pp.
Let the order of uu modulo pp be dd and pk0(ud1)p^{k_{0}} \|\left(u^{d}-1\right), then by Example 5 of Unit 8, when α>k0\alpha>k_{0}, the order of uu modulo pαp^{\alpha} is dpαk0d p^{\alpha-k_{0}}. Since uu and pp are fixed numbers, k0k_{0} and dd are also fixed numbers. If (1) has solutions for sufficiently large nn, then by (2) we know α>k0\alpha>k_{0}. From (1) we get
us1(modpα),u^{s} \equiv 1\left(\bmod p^{\alpha}\right),

hence by the property of the order, we have dpαk0sd p^{\alpha-k_{0}} \mid s; in particular, sdpαk0s \geqslant d p^{\alpha-k_{0}}. Therefore,
us1udpαk01>udpαk0k01.u^{s}-1 \geqslant u^{d p^{\alpha-k_{0}}}-1>u^{d p^{\alpha-k_{0}}-k_{0}}-1.

But when nn is sufficiently large, it is easy to see that the right-hand side of the above inequality nn1\geqslant n^{n}-1. Hence by (3) we get us1>n!u^{s}-1>n!, and thus ur(us1)>n!u^{r}\left(u^{s}-1\right)>n!, so when nn is sufficiently large, (1) has no positive integer solutions (r,s)(r, s). This completes the proof.

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.