Maths Olympiad Prep

Library / /210 of 520

Number theory Difficulty 6.0 AIME, harder Prove it

32. (i) For any positive integer kk, it must be true that 3k∣23k−1+1,3k+1∤2k−1+13^{k} \mid 2^{3^{k-1}}+1, 3^{k+1} \nmid 2^{k^{-1}}+1.
(ii) Let k,sk, s be positive integers. Prove: 3k∣2s+13^{k} \mid 2^{s}+1 if and only if
2∤s,3k−1∣s.2 \nmid s, \quad 3^{k-1} \mid s .

Solution

32. (i) Use induction; (ii) Sufficiency follows from (i). Note that when 2∣s2 \mid s, 3∤2s+13 \nmid 2^{s}+1, set s=3ts=3^{t}. f,(f,6)=1f,(f, 6)=1, use (i) to prove necessity.

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.