Maths Olympiad Prep

Library / /203 of 520

Number theory Difficulty 6.0 AIME, harder Prove it

Example 5 Let m,n,km, n, k be positive integers, n⩾m+2,kn \geqslant m+2, k be an odd number greater than 1, and p=k×2n+1p=k \times 2^{n}+1 be a prime number, p∣22m+1p \mid 2^{2^{m}}+1. Prove: k2n−1≡1( mod p)k^{2^{n-1}} \equiv 1(\bmod p).

Solution

Given that 22m≡−1( mod p)2^{2^{m}} \equiv-1(\bmod p), and n⩾m+2n \geqslant m+2, hence 2m+12^{m+1} is a factor of n⋅2n−1n \cdot 2^{n-1}, so, 2n⋅2n−1≡(−1)2t=1( mod p)2^{n \cdot 2^{n-1}} \equiv(-1)^{2 t}=1(\bmod p) (here t=n⋅2nm−2)\left.t=n \cdot 2^{n m-2}\right).

Now, from k⋅2n≡−1( mod p)k \cdot 2^{n} \equiv-1(\bmod p), we know k2n−1⋅2n⋅2n−1≡(−132n−1=1( mod p)k^{2^{n-1}} \cdot 2^{n \cdot 2^{n-1}} \equiv\left(-13^{2^{n-1}}=1(\bmod p)\right., combining the conclusion above, we can get k2n−1≡1( mod p)k^{2^{n-1}} \equiv 1(\bmod p).

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.