Maths Olympiad Prep

Library / /384 of 520

Number theory Difficulty 5.6 AIME, harder Prove it

Question 7 Let nn be a positive integer. Prove that 2n+12^{n}+1 has no prime factor that is congruent to -1 modulo 8.
(44th IMO Vietnam National Team Selection Exam)

Solution

Proof: Let p=8k1,kN+,pp=8k-1, k \in \mathbf{N}_{+}, p be a prime number, and the symbol
(1p)=1\left(\frac{-1}{p}\right)=1 \Leftrightarrow odd prime p1(mod4)p \equiv 1(\bmod 4);
(2p)=1\left(\frac{2}{p}\right)=1 \Leftrightarrow odd prime p±1(mod8)p \equiv \pm 1(\bmod 8).
From the given, we know p=7(mod8)p=7(\bmod 8), hence
(1p)=1, and (2p)=1 \left(\frac{-1}{p}\right)=-1 \text{, and }\left(\frac{2}{p}\right)=1 \text{. }

But p!(2n+1)p!\left(2^{n}+1\right), i.e., 2n1(modp)2^{n} \equiv-1(\bmod p).
Since (xp)\left(\frac{x}{p}\right) is a completely multiplicative function, we have
1=(1p)=(2np)=(2p)n=1n=1 -1=\left(\frac{-1}{p}\right)=\left(\frac{2^{n}}{p}\right)=\left(\frac{2}{p}\right)^{n}=1^{n}=1 \text{. }

Contradiction.

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.