It's Totally Totative!

Solution

Let us start with a simple observation: If n is totatively prime and $n > 4$ , then $n$ is even. This is true because the only way to make $\gcd(4,n)$ different from $1$ is to have $n$ be even. Using the same logic, $n>9$ implies that $n$ can be divided by $3$ , and in general, if $n > p^2$ for some prime $p$ , then $p$ divides $n$ .

From this, we thus conclude that if $n > p^2$ for some p, then n is a multiple of the product of all primes smaller than or equal to p. Let us make a table from this:

Note that, when $n > 49$ , $n$ has to be a multiple of $210$ . But this is itself bigger than $11^2$ , hence it would have to be a multiple of $2310$ , which is bigger than $13^2$ , and so on. We can prove (using lemma below), that if $n>49$, then $n$ is bigger than the square of any prime. There is of course no natural number for which that holds, so $n \le 49$ .

Using the table, consider the case $n>25$ . Then $n$ has to be a multiple of $30$ , and there is only one such multiple below $49$ , $30$ itself. Since any composite number below $30$ has a factor $\le 5$ , no composite number below $30$ is coprime to $30$ , hence $30$ is totatively prime. Since no number larger than it can be totatively prime, it follows that $30$ is the largest totatively prime number.

Proof of lemma

We need to show that, if $p\ge 7$ , then $\prod_{q<p} q > p^2$ .

Let $p_k$ denote the $k$-th prime. The theorem holds for $k=4$ , as seen in the table above. Suppose it holds for $p_k$ with $k\ge 4$ , then by Bertrand's postulate $p_{k+1} \le 2p_k$ . It then follows that $\prod_{q<p_{k+1}} q > 4\prod_{q<p_k} q > 4p_k^2 \ge p_{k+1}^2$ . Hence, it also follows for $p_{k+1}$ . From induction, the lemma follows.

Let $SCNC(n)$ denote the Smallest (positive) Composite Number that is Coprime to $n$ . We note that $n$ being totatively prime is equivalent to $SCNC(n)>n$ . So it begs the question, what would $SCNC(n)$ be?

First, let $P(n)$ be the set of primes that don't divide $n$ ; it is clear that the prime factorization of $SCNC(n)$ must consist of powers of primes that lie $P(n)$ . Let $p_*$ be the smallest element of $P(n)$ . If there exists $q > p_*$ such that $q$ divides $SCNC(n)$ , then we notice that $\frac{SCNC(n)*p_*}{q}$ is another composite number coprime to $n$ , and it is smaller than $SCNC(n)$ , which is a contradiction. So $SCNC(n)$ must be a prime power of $p_*$ ; in particular, it must be the smallest composite power of $p_*$ , which is $p_*^2$ .

Next, let $T$ be the set of all totatively prime numbers, and for a prime number $p$ , let $T_p := \{n \in \mathbb{N}: SCNC(n) = p^2 > n\}$ . It is clear that $T_p \subseteq T$ , and it is also clear that any element of $T$ belongs to $T_p$ for some prime $p$ . One more observation: for any $m \in T_p$ , $p$ must be the smallest prime that doesn't divide $m$ ; this implies that $m$ is divisible by every prime less than $p$ , and is thus divisible by the product of such primes. This fact allows us to quickly identity the elements of $T_p$ by simply counting up the valid multiples of the product of all primes less than $p$ . Below are the first few $T_p$ sets:

$T_2 = \{3\}$ , $T_3 = \{2,4,8\}$ , $T_5 = \{6,12,18,24\}$ , $T_7 = \{30\}$ , $T_{11} = \varnothing$ .

Why is $T_{11}$ empty? Any element of $T_{11}$ has to be a positive multiple of $2*3*5*7 = 210$ , and hence greater than $210$ . Yet, every element of $T_{11}$ must also be less than $121$ ; there are no numbers that satisfy these conditions. In general, if $p$ is the $n$ th prime number -- denote this as $q_n$ -- and $q_1q_2 \cdots q_{n-1} > q_n^2$ , then $T_{q_n}$ is empty. This fact, along with Bertrand's Postulate (actually a proven theorem regarding the distribution of primes), are enough to prove that beyond $T_7$ , all $T_p$ sets are empty; this shows that $30$ is indeed the largest totatively prime number.

Proposition : Let $q_k$ be the $k$ th prime. Then for all $k \geq 5$ , $q_1q_2 \cdots q_{k-1} > q_k^2$ (hence $T_{q_k}$ is empty for all $k \geq 5$ ).

Proof by induction. We've already evaluated the base case, namely that $2*3*5*7 = 210 > 121 = 11^2$ . So, assume that $q_1q_2 \cdots q_{k-1} > q_k^2$ for $k \geq 5$ . Then we also have that $\sqrt{q_1q_2 \cdots q_{k-1}} > q_k$ . Thus, $\sqrt{q_1q_2 \cdots q_{k-1}q_k} > q_k\sqrt{q_k}$ .

Here's where Bertrand's postulate comes in. The statement of Bertrand's postulate is that for any natural number $n$ , there exists a prime number $s$ satisfying $n < s < 2n$ . In particular the set of primes $S := \{s : q_k < s < 2q_k\}$ is nonempty and thus has a smallest element; this smallest element can be no other than $q_{k+1}$ . Since $\sqrt{q_k}>2$ whenever $k \geq 5$ , we have the following inequality chain:

$\sqrt{q_1q_2 \cdots q_k} > q_k\sqrt{q_k} > 2q_k > q_{k+1} > q_k \implies \sqrt{q_1q_2 \cdots q_k} > q_{k+1} \implies q_1q_2 \cdots q_k > q_{k+1}^2$ .

With the inductive hypothesis proven, the proposition is true. Therefore, $T_p$ is empty for any prime greater than $7$ , so $30$ is the largest totatively prime number.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from fractions import gcd
def isprime(startnumber):
    startnumber*=1.0
    for divisor in range(2,int(startnumber**0.5)+1):
        if startnumber/divisor==int(startnumber/divisor):
            return False
    return True
start_num = 3000   #starting number
primes = [] 
for a in range(2,start_num):
    if isprime(a):
        primes.append(a)
for i in range(start_num,1,-1):
    rel_prime = [k for k in range(2,i) if gcd(k,i) == 1]
    if len(list(set(rel_prime).intersection(primes))) == len(rel_prime):
        print i
        break

Ans: 30

The best way to solve this type of problem is to rephrase the question. Since it's relative prime should not be composite, we would like our number to be not a relative prime to every composite number before it. We can do that by having a number that is a multiple of all the smaller primes, so if it's a multiple of two, all even are out as a possible relative prime. If it's a multiple of 3, the all number in the form of 3n will be out as well. Soon we'll find that in this form, the possible relative prime left are those complete power of the higher prime that isn't a part of the prime divisor of our number.

Ex. 2 3 5=30; the possible number that might counter this are numbers that are powers of the next prime like 7^2, 7^3, 11^2 etc. but so far this possibilities are all more than 30.

Let's try and move ahead and go with number 2 3 5*7=210; 11^2 is less than 210 and so this would be the composite relative prime of our number... As you move higher, the numbers that counter our number increase as well. So the least number is 30.

The revised question would then be "What is the largest number that is a multiple of consecutive primes without a power of a next higher prime that is less than the number". You can use this to intuitively get the answer.