Maths Olympiad Prep

Library / /438 of 520

Number theory Difficulty 6.9 National olympiad Prove it

Example 3 Let qq be a prime factor of the Fermat number Fn=22n+1F_{n}=2^{2^{n}}+1. Prove: when n>1n>1, we have q1(mod2n+2)q \equiv 1\left(\bmod 2^{n+2}\right).

Solution

Proof
First, we prove a lemma: Let aa be a positive integer greater than 1, and qq be an odd prime factor of the number a2n+1a^{2^{n}}+1, then
q1(mod2n+1)q \equiv 1\left(\bmod 2^{n+1}\right)

In fact, from a2n1(modq)a^{2^{n}} \equiv-1(\bmod q), we know
a2n+11(modq),a^{2^{n+1}} \equiv 1(\bmod q),

This indicates that δq(a)2n\delta_{q}(a) \nmid 2^{n}, but δq(a)2n+1\delta_{q}(a) \mid 2^{n+1}. Therefore, δq(a)=2n+1\delta_{q}(a)=2^{n+1} (note that we have used q>2q>2 here). Then, by Fermat's Little Theorem, we know aq11(modq)a^{q-1} \equiv 1(\bmod q), hence 2n+1(q1)2^{n+1} \mid(q-1), i.e.,
q1(mod2n+1)q \equiv 1\left(\bmod 2^{n+1}\right)

The lemma is proved.
Returning to the original problem. When n>1n>1, note that,
Fn12n+1=(22n1+1)2n+1=(22n+21+2n1+1)2n(21+2n1)2n=(22n)1+2n1(1)1+2n11(modFn)\begin{aligned} F_{n-1}^{2^{n+1}} & =\left(2^{2^{n-1}}+1\right)^{2^{n+1}}=\left(2^{2^{n}}+2^{1+2^{n-1}}+1\right)^{2^{n}} \equiv\left(2^{1+2^{n-1}}\right)^{2^{n}} \\ & =\left(2^{2^{n}}\right)^{1+2^{n-1}} \equiv(-1)^{1+2^{n-1}} \\ & \equiv-1\left(\bmod F_{n}\right) \end{aligned}

Therefore, for a prime factor qq of FnF_{n}, we have q(Fn122+1+1)q \mid\left(F_{n-1}^{2^{2+1}}+1\right). Using the conclusion of the lemma, we get
q1(mod2n+2)q \equiv 1\left(\bmod 2^{n+2}\right)

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.