One Big Set. Topic: Number Theory. Level: Olympiad.

Problem: (1971 IMO - #3) Prove that we can find an infinite set of positive integers of the form 2^n-3 (where n is a positive integer) every pair of which are relatively prime.

Solution: We will proceed by induction, stating that given any set $ A = \{a_1,a_2,\ldots,a_k\}$ of integers of the form $ 2^n-3 $ that are pairwise relatively prime, we can find a $ a_{k+1} $ such that $ (a_i, a_{k+1}) = 1 $ for all $ 1 \le i \le k $.

Consider the set $ A = \{a_1,a_2,\ldots,a_k\} $. Let $ S = \prod a_i = a_1a_2 \cdots a_k $. Since all $ a_i $ are odd, $ S $ is odd as well and $ (S,2) = 1 $.

Hence, by Euler's Totient Theorem, we must have $ 2^{\phi(S)} \equiv 1 \pmod{S} $. Which means $ 2^{\phi(S)}-3 = mS-2 $ for some positive integer $ m $. But since all $ a_i|S $, we know $ S = r_ia_i $ for some positive integers $ r_i $. So $ (a_i, mS-2) = (a_i, mr_ia_i-2) = d_i $. So $ d_i|a_i \Rightarrow d_i|mr_ia_i $ and $ d_i|(mr_ia_i-2) \Rightarrow d_i|(mr_ia_i-(mr_ia_i-2)) $ so $ d_i|2 $. But since $ a_i $ are all odd, $ d_i $ cannot be even so $ d_i = 1 $, which means $ a_{k+1} = 2^{\phi(S)}-3 $ is relatively prime to all $ a_i $.

Therefore, we can generate an infinite number of elements of the form $ 2^n-3 $ which are pairwise relatively prime. QED.

--------------------

Comment: Euler's Totient Theorem is one of the most powerful tools in Number Theory and is a very handy thing to know for problem solving. It reduces exponents very quickly as well as having less direct applications such as in the above problem.

--------------------

Practice Problem: Evaluate $ \phi(1000) $ and find the last three digits of $ 997^{2006} $.