View source for 2008 iTest Problems/Problem 39

==Problem==

Let <math>\phi(n)</math> denote <math>\textit{Euler's phi function}</math>, the number of integers <math>1\leq i\leq n</math> that are relatively prime with <math>n</math>. (For example, <math>\phi(6)=2</math> and <math>\phi(10)=4</math>.) 
Let <math>S=\sum_{d|2008}\phi(d)</math>, where <math>d</math> ranges through all positive divisors of <math>2008</math>, including <math>1</math> and <math>2008</math>. Find the remainder when <math>S</math> is divided by <math>1000</math>.

==Solution==

The divisors of <math>2008</math> are <math>1</math>,<math>2</math>,<math>4</math>,<math>8</math>,<math>251</math>,<math>502</math>,<math>1004</math>, and <math>2008</math>, so the problem requires the sum of the number of numbers relatively prime to each of the eight numbers.

Using the formula <math>\phi(n) = n \cdot (1 - \tfrac{1}{p_1})(1 - \tfrac{1}{p_2}) \cdots (1 - \tfrac{1}{p_n})</math> (or by manually counting the numbers relatively prime to each number), <math>1</math> number is relatively prime to <math>1</math>, <math>1</math> number is relatively prime to <math>2</math>, <math>2</math> numbers are relatively prime to <math>4</math>, <math>4</math> numbers are relatively prime to <math>8</math>, <math>250</math> numbers are relatively prime to <math>251</math>, <math>250</math> numbers are relatively prime to <math>502</math>, <math>500</math> numbers are relatively prime to <math>1004</math>, and <math>1000</math> numbers are relatively prime to <math>2008</math>.  That means <math>S = 2008</math>, and the remainder when <math>S</math> is divided by <math>1000</math> is <math>\boxed{8}</math>.

==Extra Note==
If all the divisors of an integer n are {<math>{d_1}</math>,  <math>{d_2}</math>,  <math>{d_3}</math>, ... <math>{d_k}</math>}, then n  =  <math>\phi({d_1})</math> +  <math>\phi({d_2})</math> +  .... +  <math>\phi({d_k})</math>.
This provides a shorter approach in this problem because it asks about the sum of the number of numbers co prime to 2008's divisors, as mentioned earlier. This is 2008 itself.

==Proof==

Let <math>n</math> = <math>{p_1}^{\alpha_1}</math><math>{p_2}^{\alpha_2}</math>....<math>{p_k}^{\alpha_k}</math> where <math>{p_1}, {p_2}, ... {p_k}</math> are prime numbers

and 

{<math>{d_1}</math>, <math>{d_2}</math>, .... <math>{d_m}</math>} is an exhaustive, mutually exclusive list of <math>n</math>'s factors

<math>\phi({d_1})</math> + <math>\phi({d_2})</math> + ... + <math>\phi({d_m})</math> 

= <math>{p_1}(1-\frac{1}{p_1})</math> + <math>{p_2}(1-\frac{1}{p_2})</math> + <math>{p_1} {p_2}(1-\frac{1}{p_1})(1-\frac{1}{p_2})</math>...

The above term represents the sum of all the values of the the totient function applied of all of n's divisors, like the problem is asking.

= <math>(1 - \frac{1}{p_1})</math><math>(1 - \frac{1}{p_2})</math> <math>({p_1} + {p_1}^{2} + ... + {p_1}^{\alpha_1})</math> <math>({p_2} + {p_2}^{2} + ... + {p_2}^{\alpha_2})</math> + ....

= <math>(1 + (1 - \frac{1}{p_1})</math><math>({p_1} + {p_1}^{2} + ... + {p_1}^{\alpha_1})</math>)<math>(1 + (1 - \frac{1}{p_2})</math><math>({p_2} + {p_2}^{2} + ... + {p_2}^{\alpha_2})</math>) ... <math>(1 + (1 - \frac{1}{p_k})</math><math>({p_k} + {p_k}^{2} + ... + {p_k}^{\alpha_k})</math>

= <math>(1 + {p_1} + {p_1}^{2} + ... + {p_1}^{\alpha_1} - (1 + {p_1} + {p_1}^{2} + ... + {p_1}^{\alpha_1 - 1}))</math> x

<math>(1 + {p_2} + {p_2}^{2} + ... + {p_2}^{\alpha_2} - (1 + {p_2} + {p_2}^{2} + ... + {p_2}^{\alpha_2 - 1}))</math> x ...

<math>(1 + {p_k} + {p_k}^{2} + ... + {p_k}^{\alpha_k} - (1 + {p_k} + {p_k}^{2} + ... + {p_k}^{\alpha_k - 1}))</math>

= <math>{p_1}^{\alpha_1}</math><math>{p_2}^{\alpha_2}</math> ... <math>{p_k}^{\alpha_k}</math>

= <math>n</math>

==See Also==
{{2008 iTest box|num-b=38|num-a=40}}

[[Category:Introductory Number Theory Problems]]