Maths Olympiad Prep

Library / /53 of 97

Number theory Difficulty 8.0 Shortlist Find the answer

For any positive integer dd, prove there are infinitely many positive integers nn such that d(n!)1d(n!)-1 is a composite number.

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

Solution

For any positive integer d d , we aim to prove that there are infinitely many positive integers n n such that d(n!)1 d(n!) - 1 is a composite number.

### Case 1: d=1 d = 1

Assume for the sake of contradiction that for all sufficiently large nN n \in \mathbb{N} , n!1 n! - 1 is prime. Define pn=n!1 p_n = n! - 1 to be this prime for all nN n \geq N for some NN N \in \mathbb{N} . Notice that pn>n p_n > n . Consider n=pnkn n = p_n - k_n for some knN k_n \in \mathbb{N} .

In Fpn \mathbb{F}_{p_n} , by Wilson's Theorem, we have:
1=(pnkn)!=(pn1)!(pn1)(pn2)(pnkn+1)=1(1)kn1(kn1)!=(1)kn1(kn1)! 1 = (p_n - k_n)! = \frac{(p_n - 1)!}{(p_n - 1)(p_n - 2) \cdots (p_n - k_n + 1)} = \frac{-1}{(-1)^{k_n - 1} \cdot (k_n - 1)!} = (-1)^{k_n} \cdot \frac{1}{(k_n - 1)!}
Thus,
(kn1)!(1)kn(modpn) (k_n - 1)! \equiv (-1)^{k_n} \pmod{p_n}
If we pick n1(mod2) n \equiv 1 \pmod{2} , then knpnn0(mod2) k_n \equiv p_n - n \equiv 0 \pmod{2} as pn p_n is odd, and therefore pn(kn1)!1 p_n \mid (k_n - 1)! - 1 .

Since kn>C k_n > C for all sufficiently large nN n \in \mathbb{N} for any CN C \in \mathbb{N} , and considering the pigeonhole principle, we conclude that pn=(kn1)!1 p_n = (k_n - 1)! - 1 . Hence, pn=n!1 p_n = n! - 1 implies pnn1=kn1=n p_n - n - 1 = k_n - 1 = n , which means pn=2n+1 p_n = 2n + 1 . This implies 2n+1=n!1 2n + 1 = n! - 1 for infinitely many nN n \in \mathbb{N} , which is impossible for large n n . Therefore, n!1 n! - 1 cannot be prime for all sufficiently large n n .

### General Case: d2 d \geq 2

Assume for the sake of contradiction that there exists some NN N \in \mathbb{N} such that for all nN,nN n \in \mathbb{N}, n \geq N , dn!1 d \cdot n! - 1 is prime. Define the function f:N[d]N f: \mathbb{N} \setminus [d] \to \mathbb{N} as:
f(m)=(d1)!(d+1)(d+2)(m1)m+(1)m f(m) = (d-1)! \cdot (d+1)(d+2) \cdots (m-1) \cdot m + (-1)^m

Let pm p_m be the smallest prime divisor of f(m) f(m) . For m2d m \geq 2d , pm>m p_m > m because gcd(m!,f(m)1)d \gcd(m!, f(m) - 1) \mid d but df(m) d \mid f(m) implies gcd(f(m)1,d)=1 \gcd(f(m) - 1, d) = 1 . Thus, pmf(m)+(1)m p_m \mid f(m) + (-1)^m , meaning:
0d(f(m)+(1)m)m!+d(1)m(modpm) 0 \equiv d(f(m) + (-1)^m) \equiv m! + d(-1)^m \pmod{p_m}

Using Wilson's Theorem in Fpm \mathbb{F}_{p_m} :
(pmm1)!=(pm1)!(pm1)(pm2)(pmm)=1(1)mm!=1(1)m((1)m)d=1d (p_m - m - 1)! = \frac{(p_m - 1)!}{(p_m - 1)(p_m - 2) \cdots (p_m - m)} = \frac{-1}{(-1)^m \cdot m!} = \frac{-1}{(-1)^m (-(-1)^m) \cdot d} = \frac{1}{d}
Thus,
pmd(pmm1)!1 p_m \mid d(p_m - m - 1)! - 1

For sufficiently large m m , pm=d(pmm1)!1 p_m = d \cdot (p_m - m - 1)! - 1 . By the pigeonhole principle, km=pmm k_m = p_m - m can appear finitely many times. Therefore, kmN+1 k_m \geq N + 1 implies d(pmm1)!1 d \cdot (p_m - m - 1)! - 1 is prime, leading to a contradiction.

Hence, for any positive integer d d , there are infinitely many positive integers n n such that d(n!)1 d(n!) - 1 is a composite number.

The answer is: \boxed{\text{There are infinitely many positive integers } n \text{ such that } d(n!) - 1 \text{ is a composite number.}}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.