Minimum Totient Quotient

Given an integer $N=p_1^{q_1}p_2^{q_2}...p_n^{q_n}$ , $\phi N=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_n})$ . Thus, $\frac{\phi N}{N}=(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_n})$ . Each of these expressions in the parentheses is less than one, so the more of these terms there are, the smaller their product will be. In addition, $(1-\frac{1}{p_i})$ will be closest to zero when $p_i$ is closest to one, so we want small prime factors. A number composed of small primes will have each term be smaller and allow more terms to fit before the number exceeds one thousand. Thus, we start with the first prime, two, and repeatedly multiply until we find the greatest number that is still under one thousand. This number turns out to be $2\times3\times5\times7=210$ , which has a totient quotient of $\frac{8}{35}$ . 210 is also the smallest number that can get such a totient quotient, because it has exactly one of each prime factor. Any multiples of the number less than one thousand would be larger, but still have the same totient quotient because they still only have those four prime factors. Thus, the answer is 210.

Let $f(n)$ be the euler phi function for n to save on formatting. If a and b are coprime, $f(a)f(b) = f(ab)$ . Also, note that $f(p^k)/(p^k) = (p-1)/p$ for all prime $p$ , and all positive integers $k$ .

Thus if n is minimal s.t. $f(n)/n$ is minimal, if we factor it into $(p_1^{q_1})*(p_2^{q_2})...*(p_m^{q_m})$ , by the previous observation all $q_i$ are 1. Thus $n = p_1*p_2*...*p_m$ (these primes are ordered $p_1 < p_2 < ... < p_m$ ). Note that $(p-1)/p$ is strictly increasing as $p$ increases and is always less than 1; the former observation implies that there exists no prime q between $p_k$ and $p_{k+1}$ s.t. $q$ is not in $p_i$ ; while the second observation implies that $1000 < p1*p2*...*pm*q$ for any prime $q > pm$ since the value of $f(n*q)/(n*q)$ is smaller. Thus the answer is just $2*3*5*7 = 210$ .

We factorize $n$ such that: $n = p_1^{q_1}p_2^{q_2}\ldots p_k^{q_k}$ , where $p_1, p_2, \ldots, p_k$ are distinct prime factors of $n$ and $q_1, q_2, \ldots, q_k$ are positive integers. So, we have $\phi(n) = n\cdot \left(\frac{p_1-1}{p_1}\right)\left(\frac{p_2-1}{p_2}\right)\ldots \left(\frac{p_n-1}{p_k}\right)$ . Thus $\frac{\phi(n)}{n} = \left(\frac{p_1-1}{p_1}\right)\left(\frac{p_2-1}{p_2}\right)\ldots \left(\frac{p_k-1}{p_k}\right)$ . This implies that the value of $\frac{\phi(n)}{n}$ is not dependent on the exponents of the prime factorization of $n$ , hence to minimize it we set $q_1 = q_2 = \ldots = q_k = 1$ .

We have $\frac{r-1}{r} < \frac{s-1}{s} \Leftrightarrow \frac {1}{s} < \frac {1}{r} \Leftrightarrow r < s$ . Thus this product is minimized by taking smallest $k$ prime factors, and as many of them as possible. Hence we have $n = 2^1\cdot 3^1 \cdot 5^1 \cdot 7^1 = 210$ as the smallest possible value.

Euler's Phi Function is defined as followed: If n is a positive integer, phi(n) is the number of integers k, 1<=k<=n-1, such that (n, k)=1. The formula for phi(n) where n=p 1^e 1 + p 2^e^2 + . . . + p m^e m is (1-1/p 1) (1-1/p_2) . . . (1-1/p_m) n, where each p i are distinct and prime. Now, we see that phi(n)/n=(1-1/p 1) (1-1/p_2) . . .*(1-1/p m). To minimize this, we wish to have as many prime factors as possible in n to make the product smaller and smaller. Also, the factor (1-1/p i) is minimized when p_i is smaller. Choosing the most possible amount of the first consecutive primes (i.e. the smallest primes) for n while keeping n less than 1000, we find that n=2x3x5x7=210, our desired answer.

210= 2\times3 \times 5 \times 7 you might conjecture that for 1 \leq n \leq m , the value minimizing \frac {phi( n )}{ n } is the smallest primorial less than or equal to m .

This conjecture is in fact true and easy to prove if you know that \phi( n ) is multiplicative and when p is prime.

We can rewrite $\frac{\phi(n)}{n}$ as $\frac{(p_1-1)}{p_1}\frac{(p_2-1)}{p_2}...\frac{(p_k-1)}{p_k}$ by the definition of the phi function, where $p_i$ are the prime factors of $n$ .

Therefore, to minimize this, we just want to maximize the number of prime factors and put them as small as possible.

The maximum number of prime factors we can have is 4 if we choose 2, 3, 5, 7 so our number is $210$ .

Note that if $n=p_1^{e_1}\cdots p_i^{e_i}$ is the prime factorization of $n$ , then $\phi(n)=n\cdot \frac{p_1-1}{p_1}\cdots\frac{p_i-1}{p_i}$ . So if $p\mid n$ , then $\dfrac{\phi(pn)}{pn}=\dfrac{\phi(n)}{n}$ . Hence the minimal $n$ is a product of distinct primes. Also note that $\frac{x-1}{x}$ is a strictly increasing function, so we wish for the prime factors of $n$ to be as small as possible. Some calculation yields $n=2\cdot 3\cdot 5\cdot 7=\boxed{210}$ .

I'm not good at number theory, therefore python will save me xD

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def hcf(arg1, arg2):
    i = 1
    k = 1
    while i <= arg1:
        if ((arg1%i == 0) & (arg2%i == 0)):
            k = i
        i += 1
    return k

def totient(num):
    i=1
    s=0
    while i <= num:
        if hcf(num,i) == 1:
            s += 1
        i += 1
    return s

min=1
f=1
p=1
while p<=1000:
    if totient(p)/p < min:
        min = totient(p)/p
        f=p
    p += 1

print(f)

The code takes some time to show the output though.

A very important idea here is that the number of different prime factors of a number less than or equal to 1000 is 4. If a natural number $n$ less than or equal to 1000 had, for example, 5 different prime factors, then assuming that the prime factors are $p_1, p_2, p_3, p_4, p_5,$ given in an increasing order, we will have that $p_1 \geq 2,$ $p_2\geq 3,$ $p_3\geq 5,$ $p_4\geq 7,$ $p_5\geq 11.$ Therefore, $n\geq p_1 p_2 p_3 p_4 p_5\geq 2*3*5*7*11=2310,$ that is contradiction. Now, we can find the minimum value of $\frac{\phi(n)}{n}$ assuming that an expression of the form $(1-1/x)$ is increasing for $x>0,$ and, therefore, we can make the following conclusions. When $n$ has only one prime factor the minimum value must be $(1-1/2)=1/2.$ If $n$ has two prime factors, then the minimum would be $(1-1/2)(1-1/3)=1/3.$ For the case when $n$ has three or four factors, the minimum values would be $(1-1/2)(1-1/3)(1-1/5)=4/15$ or $(1-1/2)(1-1/3)(1-1/5)(1-1/7)=8/35,$ respectively. Out of these four numbers the smallest is $8/35.$ So the minimum is attained at a number $n$ with prime factors $2, 3, 5, 7,$ and then the smallest possible value of $n$ is $2*3*5*7=210.$

for n = 210 , 420 , 630, ... given ratio is minimized . Among them , 210 is the smallest n :)

If $n=a_1^{b_1} a_2^{b_2} \ldots a_n^{b_n}$ , where $a_1 a_2 \ldots a_n$ are primes and $b_1 b_2 \ldots b_n$ are non-negative integers, $\phi(n)=(a_1-1)a_1^{b_1-1}(a_2-1)a_2^{b_2-1}\ldots (a_n-1)a_n ^{b_n-1}$ . Hence, $\frac{\phi(n)}{n}=\frac{(a_1-1)}{a_1} \frac{(a_2-1)}{a_2}\ldots \frac{(a_n-1)}{a_n}$ . This implies that $\frac{\phi(n)}{n}$ decreases as the number of prime divisors increases, and is the same regardless of the power of the prime factors. As such, we want to get as many primes as possible: $2 \times 3 \times 5 \times 7=210$ while $2 \times 3 \times 5 \times 7 \times 11>1000$ . Hence, $n=210$ .

$\frac {\phi(n)}{n}$ = $\frac {n \times \displaystyle\sum_{i=2}^n \frac {p-1}{p}}{n}$

$= (\frac {p-1}{p} )(\frac{p{2} -1} {p{2}}).....(\frac{pn-1}{pn})$

Here n is given to be least integer less than 1000, therefore we conclude each prime p divide n only one once

Second $n = p\times(p2)....(pn)$ here n less than 1000

as p occurs only once therefore $n=(2)(3)(5)(7) = 210$ as if the next prime 11 is multiplied, $n$ exceeds 1000. $n=210$

[Student revision]

First , let us write n as $n=p^a\times q^b+\ldots$ , where p,q… are prime numbers. The formula for calculating $\phi(n)$ is $\phi(n)=n(1-1/p)(1-1/q)+\ldots$ .Putting both these values in our fraction , we get $\phi(n)/n=((p-1)/p\times (q-1)/q+(ldots$ . Rearranging the expression, (p-1)(q-1)+ ldots/)\(p^{a+1}\times q(b+1) + \ldots . Since we want the minimum the value of n less than 1000, we want the value of the numerator to be least and the denominator to be maximum. For the numerator to be minimum, all p,q,..., should be as small as possible, and as they are prime numbers, the should be 2,3,.... Now for the denominator to be maximum, let the values of a,b,... be 1. Now looking at prime numbers, the product of 2,3,5,7,11, exceeds 1000, therefore we will have to consider of the first four only which comes to be 210.