## Tuesday, January 17, 2006

### 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}$.

#### 1 comment:

1. phi(1000) = 400
997^2006 mod 1000 = (-3)^6 mod 1000 = 729
wooooo negative modular arithmetic