Maths Olympiad Prep

Library / /467 of 520

Number theory Difficulty 7.0 National olympiad, round 2 Prove it

33. Let m3m \geqslant 3. Prove the following: the arithmetic sequence 1+lm(l=0,1,)1+\operatorname{lm}(l=0,1, \cdots) must contain infinitely many primes. (i) The original proposition is equivalent to the statement that the arithmetic sequence must contain at least one prime. (ii) Let qq be a prime, qmm1\mathrm{q} \mid m^{m}-1 and δq(m)=h\delta_{q}(m)=h, then qrmh1q^{r} \| m^{h}-1 if and only if qrmm1q^{r} \| m^{m}-1. (iii) If qq satisfies the conditions in (ii) and mq1m \nmid q-1, then h<mh < m. (iv) Let the distinct prime factors of mm be p1,p2,,pnp_{1}, p_{2}, \cdots, p_{n}; and let the sets be
S1={s=m/(pi1pit):1i1<<itn,2t}S2={s=m/(pi1pit):1i1<<itn,2t}\begin{array}{l} S_{1}=\left\{s=m /\left(p_{i_{1}} \cdots p_{i_{t}}\right): 1 \leqslant i_{1}<\cdots<i_{t} \leqslant n, 2 \nmid t\right\} \\ S_{2}=\left\{s=m /\left(p_{i_{1}} \cdots p_{i_{t}}\right): 1 \leqslant i_{1}<\cdots<i_{t} \leqslant n, 2 \mid t\right\} \end{array}

and
A1=sS1(ms1),A2=sS2(ms1)A_{1}=\prod_{s \in S_{1}}\left(m^{s}-1\right), \quad A_{2}=\prod_{s \in S_{2}}\left(m^{s}-1\right)

Prove: If all prime factors qq of mm1m^{m}-1 are not congruent to 1(modm)1 \pmod{m}, then we must have A1=(mm1)A2A_{1} = \left(m^{m}-1\right) A_{2}. (v) When m3m \geqslant 3, the equation in (iv) cannot hold. Therefore, the arithmetic sequence must contain at least one prime.

Solution

33. (ii) Prove the necessity by contradiction. If qr+1mm1q^{r+1} \mid m^{m}-1, then it must be that qmq \mid m, which is a contradiction; (iv) The prime factors of A1,A2A_{1}, A_{2} must be the prime factors of mm1m^{m}-1. Let qq be a prime factor of mm1m^{m}-1, δq(m)=h\delta_{q}(m)=h. Then, qms1(sS1q \mid m^{s}-1\left(s \in S_{1}\right. or S2)\left.S_{2}\right) if and only if hsh \mid s, and qrms1q^{r} \| m^{s}-1, where rr is the same as in (ii). Suppose qr1A1,qr2A2,m=hcq^{r_{1}}\left\|A_{1}, q^{r_{2}}\right\| A_{2}, m=h c, and the number of distinct prime factors of cc is kk. Prove that when mq1m \nmid q-1, we have r1={(k1)+(k3)+}r,r2={(k2)+(k4)+}rr_{1}=\left\{\binom{k}{1}+\binom{k}{3}+\cdots\right\} r, r_{2}=\left\{\binom{k}{2}+\binom{k}{4}+\cdots\right\} r. Consequently, r1r2=rr_{1}-r_{2}=r; (v) Let S0S_{0} be the smallest positive integer in the union S1S2S_{1} \cup S_{2}. Take the congruence A1=(mm1)A2A_{1}=\left(m^{m}-1\right) A_{2} modulo m20+1m^{2} 0^{+1}. Prove that when m3m \geqslant 3, regardless of whether s0S1s_{0} \in S_{1} or S2S_{2}, this congruence does not hold.

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.