## Euler’s totient function, $\phi(n)$ [sometimes called the phi function], is defined as the number of positive integers not exceeding $n$ which are relatively prime to $n$. For example, as $1$, $2$, $4$, $5$, $7$, and $8$, are all less than or equal to nine and relatively prime to nine, $\phi(9)=6$.

$n$

Relatively Prime

$\phi(n)$

$n/\phi(n)$

2

1

1

2

3

1,2

2

1.5

4

1,3

2

2

5

1,2,3,4

4

1.25

6

1,5

2

3

7

1,2,3,4,5,6

6

1.1666…

8

1,3,5,7

4

2

9

1,2,4,5,7,8

6

1.5

10

1,3,7,9

4

2.5

It can be seen that $n = 6$ produces a maximum $n/\phi(n)$ for $n\leq 10$.

Find the value of $n\leq 1\,000\,000$ for which $n/\phi(n)$ is a maximum.

### Given the mathematical task, it is quite obvious that we need to maximize the function $\frac{n}{\phi(n)}$. Euler’s Totient Function, $\phi(n)$, counts the positive integers up to a given integer $n$ that are relatively prime to $n$.

On examining the problem, observe that $n/\phi(n)$ gets maximized when $\phi(n)$ is minimized (keeping $n$ constant). To minimize $\phi(n)$, we need to maximize the count of numbers that divide $n$ (since less numbers would be relatively prime to $n$).

One way to do this is choose a number composed of a product of increasing primes. Given $n\leq 1\,000\,000$, a simple way to approach this would be to multiply primes until we get the largest result below 1,000,000:

$2 \times 3 = 6$

$2 \times 3 \times 5 = 30$

$2 \times 3 \times 5 \times 7 = 210$

$2 \times 3 \times 5 \times 7 \times 11 = 2310$

$2 \times 3 \times 5 \times 7 \times 11 \times 13 = 30030$

$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 510510$

If we try to multiply by 19, the next prime number, the result is greater than 1,000,000, so the largest value of $n$ under 1,000,000 for which $n/\phi(n)$ is a maximum is $n = 510510$.

##### More Answers:

Diophantine EquationMaximum Path Sum II

Magic 5-gon Ring