Coprime Couples

Simply enough, $\sum_{n=1}^{20} \phi(n) = \boxed{128}$ , where $\phi(n)$ is Euler's totient function. This sum follows readily from the definition of $\phi$ .

Let $\gcd(n,m) = d$ . First, assume $n \ne m$ .

Let us consider the non-coprime pairs of positive integers.

If $2|d$ , then $m,n \in {2,4, \cdots , 20}$ . There are $\dbinom{10}{2} = 45$ possible ways this can happen. If $3|d$ , then $m,n \in {3,6, \cdots , 18}$ . There are $\dbinom{6}{2} = 15$ possible ways this can happen. If $5|d$ , then $m,n \in {5,10,15,20}$ . There are $\dbinom{4}{2} = 6$ possible ways this can happen. If $7|d$ , then $m,n \in {7,14}$ . There is $1$ way this can happen. And if none of these hold, $d$ must divide a prime above $7$ , but no two distinct numbers from $1$ to $20$ share a prime factor above $7$ .

Now we account for overcounts. If $2|d$ and $3|d$ , then $6|d$ , so $m,n \in {6,12,18}$ . There are $\dbinom32 = 3$ ways this can happen. If $2|d$ and $5|d$ , then $10|d$ , so $m,n \in {10,20}$ . There is only one way this can happen. If $2|d$ and $7|d$ , then $14|d$ , which is impossible. If $3|d$ and $5|d$ , then $15|d$ , which is impossible. If $3|d$ and $7|d$ , then $21|d$ , which is impossible. If $5|d$ and $7|d$ , then $35|d$ , which is impossible. Also, we can notice that no three of these conditions can simultaneously occur. Therefore, the complement of our answer is $45 + 15 + 6 + 1 - 3 - 1 = 63$ .

The total number of ways we can choose $m,n$ is $\dbinom{20}{2} = 190$ . Therefore, we $190 - 63 = 127$

However, at the beginning we said $n \ne m$ . Now when $n = m$ , we get $d = n = m = 1$ , so we have to add another solution, bringing our total to the final answer $\boxed{128}$

In number theory, Euler's totient or phi function, φ(n) is an arithmetic function that counts the number of positive integers less than or equal to n that are relatively prime to n. There are several formulae for the totient. Euler's product formula states: φ(n)=n* Π(1-1/p), where the product is over the distinct prime numbers dividing n. In our problem we have to count φ(1)+ φ(2)+...+φ(20). Using Euler's product formula we get our result.

for 1 all the numbers will be co prime to it.so it counts to 20. for 2 all odd numbers will be co prime.so 20/2=10. for 3 all nos not divisible by 3.17-(17/3)=9 for 4 all odd numbers will be co prime. so (20- 4)-(16/4). and going on like that.

make a chart of all co prime which satisfies the above relation and then count the no. of co prime and you will get the answer.

> We denote $A_i$ as the set comprises of pairs of intergers $(n,m)$ which sastify that : $1 \le n \le m \le 20 ; i| gcd( n,m)$ . > Thus, since $\{ n | 1 \le n \le 20 ; i|n \} = [ \frac{20}{i}]$ ( $i$ is an positive integer), we imply that: $|A_i|=\frac{ [20/i]( [20/i]+1)}{2}$ (1) > On the other hands, we have that: $\{(n,m)| 1< gcd(n,m) ;1 \le n \le m \le 20 \}= \cup_{ p \in \mathbb{P} ; p<20} A_p$ > According to Inclusion-Exclusion principle ,we have: $|\cup_{ p \in \mathbb{P} ; p<20}  A_p |=$ $(\sum_{p \in \mathbb{P},p<20} |A_p| )-$

$(\sum_{p<q; p,q \in \mathbb{P} ; p,q<20}$ $|A_p \cap A_q| )$ $=82$ [ according to (1) ]

And there are $210$ pairs of integers $(n,m)$ which sastify that: $1 \le n \le m \le 20$ Hence, $210-82=128$ is our desired number

One way to go about answering this question is by creating a list of numbers and then counting how many pairs there are.

The first list is the numbers 1 to 20.

For all $1\leq n \leq 20$ you can count the number of possibilities for m, keeping in mind n and m are coprime and that $n\leq m \leq 20$

You'll get something like this:

$n=1, |M| = 20$

$n=2, |M| = 9$

$n=3, |M| = 12$

$n=4, |M| = 8$

$n=5, |M| = 12$

$n=6, |M| = 5$

$n=7, |M| = 12$

$n=8, |M| = 6$

$n=9, |M| =8$

$n=10, |M| = 4$

$n=11, |M| = 9$

$n=12, |M| = 3$

$n=13, |M| = 7$

$n=14, |M| = 3$

$n=15, |M| = 3$

$n=16, |M| = 2$

$n=17, |M| = 3$

$n=18, |M| = 1$

$n=19, |M| = 1$

$n= 20, |M| = 0$

Where $|M|$ is the cardinality of the set of M, or in other words the number of elements in M, and M is the set of possible values of m for that value of n.

Important things to keep in mind when compiling this list are the patterns on numbers like primes and various multiples, with the exception of 1. Then, you add up the numbers and get:

$20+9+12+8+12+5+12+6+8 = 92$

$92+4+9+3+7+3+3+2+3+1+1+0 = 128$

[Split up so that the adding doesn't go off the page]

And so 128 is the answer.

$m=20\implies n=1,2,...,20\to 20$ choices $m=19\implies n=1,2,...,19\to 19$ choices .

.

.

$m=1\implies n=1\to 1$ choice

Total $=1+2+...+20=210$ .

We find all pairs with $gcd>1$ :

$2\to 2,4,6,...,20=10$ choices

$3\to 3,6,9,..,18=6$ choices

.

( Similarly we can calculate for all numbers )

.

$20\to 20=1$ choice.

Total $=10+6+...+1=82$ .

So required number $=128$ .

$\displaystyle \sum_{i=1}^{20} \phi(i)=128$

why not python?

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

def gcd(m, n):
    if m==0:
        return n
    while m!=0:
        n%=m
        m,n=n,m
    return n

count=0
for i in xrange(1, 21):
    for j in xrange(i, 21):
        if gcd(i, j)==1:
            count+=1

print count

Euler Totient Fuction, denoted as $\varphi(m)$ , is a function that takes any integer, and gives the amount of integers less than or equal to $m$ that are coprime to it.

We have $1<=n<=m<=20$ and if n=m, the greatest common divisor is not 1. Thus, can set m equal to each of the integers from 1 to 20, since for each phi(n)=k, k<=n (Equality when n=1) By direct calculation, the number of pairs is, phi(20)+phi(19)+phi(18)....phi(1)=128

Sum up the results of Euler's Totient function when operated on integers ranging from 1 to 20. This will give the result.

The totient function when operated on a number "n" gives the total count of numbers those are less than and coprime to "n".

This function is defined as

$f(n)$ = $n$ $\prod_{i=1}^{k}$ (1-1/ $p_{i}$ ) where f(n) is the totient function, "n" is the number in context for which the coprime count less than that needs to be computed and $p_{1}, p_{2},\ldots,p_{k}$ are the prime factors of the number "n".

Eg: $f(20)=20(1-1/2)(1-1/5) = 8$

Hence the solution is $\sum_{n=1}^N f(n)$ , in this case $N=20$ this would yield a result of $128$ .

$\varphi(m)$ = number of positive integers less than n that are relatively prime to n. (1). phi(p) where p is prime = p-1 (2). phi is multiplicative, so if n= i.j and gcd(i,j)=1, then phi(n) = phi(i). phi(j) (3). phi(p^k) where p is a prime = (p^(k-1)). (p-1) Now, 1...20 has 8 primes (2,3,5,7,11,13,17,19). phi(n) for them can be computed using (1) For the rest, formula (2) and (3) can be used. Also phi(1) =1. Then we need to sum up all phi(n), n ranging from 1 to 20. and we will get the answer.

The number of $n$ which is coprime to $m$ is $\varphi(m)$ . So, to get the result we need only count $\sum_{m=1}^{20}\varphi(m)$ . To find $\varphi(m)$ , we can either list them (since it's not really a brute force) or use the Euler's product formula: $\displaystyle \varphi(m) = m\prod_{p\|m}(1 - \frac{1}{p})$ where $p$ 's are prime factors of $m$ and $\varphi(1) = 1$ .

So, $\varphi(1) = 1,\\ \varphi(2) = 1,\\ \varphi(3) = 2,\\ \varphi(4) = 2,\\ \varphi(5) = 4,\\ \varphi(6) = 2,\\ \varphi(7) = 6,\\ \varphi(8) = 4,\\ \varphi(9) = 6,\\ \varphi(10) = 4,\\ \varphi(11) = 10,\\ \varphi(12) = 4,\\ \varphi(13) = 12,\\ \varphi(14) = 6,\\ \varphi(15) = 8,\\ \varphi(16) = 8,\\ \varphi(17) = 16,\\ \varphi(18) = 6,\\ \varphi(19) = 18,\\ \varphi(20) = 8.$

So, summing it all up giving us $128$ .