Maths Olympiad Prep

Library / /6 of 17

Number theory Difficulty 4.9 AIME Prove it Bulgaria

Sn={aa<n,kN:2ka(modn)}S_n = \{a \mid a < n, \exists k \in \mathbb{N} : 2^k \equiv a \pmod{n}\}.

Are there different odd numbers mm and rr such that Sm=SrS_m = S_r?

Solution

No! There exists a natural number ss such that 2s1(modn)2^s \equiv 1 \pmod{n} (for example s=φ(n)s = \varphi(n) from Euler's theorem or because the power series of 22 modulo nn is periodic). We have 2s1n+12(modn)2^{s-1} \equiv \frac{n+1}{2} \pmod{n} and so x=n+12Snx = \frac{n+1}{2} \in S_n, but 2x=n+1>n2x = n+1 > n is not in SnS_n. Also, if tn12t \le \frac{n-1}{2} is of SnS_n, then 2t<n2t < n is also. Therefore, the smallest natural number tt such that tSnt \in S_n and 2tSn2t \notin S_n, is n+12\frac{n+1}{2}. Since this number is different for different nn, we get what we asked for. \square

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.