Rational and Irreducible

Number Theory Level 2

Let $f : \mathbb{Z}^+ \longrightarrow \mathbb{Z}^*$ the function that assigns to each positive integer $n$ the number of rational numbers $\frac{p}{q}$ such that $\left\lbrace \begin{array}{ccc} p+q = n \\ 0<\frac{p}{q}<1 \\ \gcd(p,q)=1. \end{array}\right.$ For example, when $n=8,$ we have $2$ such rational numbers: $\frac{1}{7}$ and $\frac{3}{5}$ . Hence $f(8)=2$ .

What is the first positive integer $m$ such that there is no solution to $f(n)=m?$

The answer is 7.

6 solutions

Arjen Vreugdenhil
Feb 25, 2018

Claim 1 : $m = f(n) = \tfrac12\phi(n)$ , where $\phi$ is the Euler totient function.

Proof: By definition, $\phi(n)$ is the number of values $1 \leq x < n$ that are coprime to $n$ .

Let $1 \leq p < \tfrac12n$ be coprime to $n$ , and $q = n - p$ . Then $p/q$ satisfies the given condition. (As for the third condition: if $\gcd(p,q) = g$ then $g$ must be a divisor of $n$ as well as $p$ . However, $n$ and $p$ are coprime. Therefore $g = 1$ .)

Conversely, suppose $p, q$ satisfy the given conditions. Let $g = \gcd(p,n)$ . Then $g$ also divides $q = n - p$ . But $p$ and $q$ are coprime; therefore $g = 1$ . The same reasoning shows that $q$ is coprime to $n$ .

Thus the numerators and denominators of these $p/q$ are precisely the set of values between $1 \leq x < n$ that are coprime to $n$ ; and therefore there are $\tfrac12\phi(n)$ such fractions.

Claim 2 : The smallest $m$ that cannot be written in this form is $m = 7$ .

We have $2 = \phi(3);\ \ 4 = \phi(5);\ \ 6 = \phi(7);\ \ 8 = \phi(16);\ \ 10 = \phi(11);\ \ 12 = \phi(13),$ so that $m = 1,\dots, 6$ are accounted for.

If $\phi(n) = 2\cdot 7 = 14$ , it must be a product of factors of the form $p^{e-1}(p-1)$ , where $p$ is a prime number. This requires one of the following:

$p = 7$ ; but this generates a factor equal to at least $7^1\cdot 6 = 42$ .
$p - 1 = 7$ ; but 8 is not a prime number.
$p = 14$ ; but this is not a prime number.
$p - 1 = 14$ ; but 15 is not a prime number.

Therefore the equation $\phi(n) = 14$ has no solution, and $m = \boxed{7}$ cannot be generated.

[ This comment has been converted into a solution ]

Michael Fitzgerald - 3 years, 3 months ago

The formula $f(n) = \frac12 \phi(n)$ is true for $n\ge 3,$ but it fails for $n=1,2.$

Patrick Corn - 3 years, 3 months ago

That is true.

Arjen Vreugdenhil - 3 years, 3 months ago

Michael Fitzgerald
Feb 27, 2018

import collections

max_n= 100

def gcd(x, y):
    gcd = 1  
    if x % y == 0:
        return y   
    for k in range(int(y / 2), 0, -1):
        if x % k == 0 and y % k == 0:
            gcd = k
            break  
    return gcd

m = []
for i in range(2,max_n+1):
    nums = [x for x in range(1,i)]
    integer_counts = collections.Counter(nums)
    count = 0
    for x in nums:
        y = i - x
        if x < y and integer_counts[y] and gcd(x,y) == 1:
            if i in [8,15,45]:  # print a sample of tuples
                print '\t\tf(%d) #%d\t%s' %(i,count+1, (x,y))
            count += 1
            integer_counts.subtract((x, y))
    print 'f(%d) = %d' %(i, count)
    if count not in m:
        m.append(count)

list_ = set(range(max_n+1))-set(sorted(m))
print "\n\nUnique list of m's with no solution for n (1, %d): \n%s....." \
        %(max_n,",".join(str(i) for i in list(list_)[:5]))

print '\n\nSmallest m = %d' %(min(list_))

f(2) = 0
f(3) = 1
f(4) = 1
f(5) = 2
f(6) = 1
f(7) = 3
                f(8) #1 (1, 7)
                f(8) #2 (3, 5)
f(8) = 2
f(9) = 3
f(10) = 2
f(11) = 5
f(12) = 2
f(13) = 6
f(14) = 3
                f(15) #1        (1, 14)
                f(15) #2        (2, 13)
                f(15) #3        (4, 11)
                f(15) #4        (7, 8)
f(15) = 4
f(16) = 4
f(17) = 8
f(18) = 3
f(19) = 9
f(20) = 4
f(21) = 6
f(22) = 5
f(23) = 11
f(24) = 4
f(25) = 10
f(26) = 6
f(27) = 9
f(28) = 6
f(29) = 14
f(30) = 4
f(31) = 15
f(32) = 8
f(33) = 10
f(34) = 8
f(35) = 12
f(36) = 6
f(37) = 18
f(38) = 9
f(39) = 12
f(40) = 8
f(41) = 20
f(42) = 6
f(43) = 21
f(44) = 10
                f(45) #1        (1, 44)
                f(45) #2        (2, 43)
                f(45) #3        (4, 41)
                f(45) #4        (7, 38)
                f(45) #5        (8, 37)
                f(45) #6        (11, 34)
                f(45) #7        (13, 32)
                f(45) #8        (14, 31)
                f(45) #9        (16, 29)
                f(45) #10       (17, 28)
                f(45) #11       (19, 26)
                f(45) #12       (22, 23)
f(45) = 12
f(46) = 11
f(47) = 23
f(48) = 8
f(49) = 21
f(50) = 10
f(51) = 16
f(52) = 12
f(53) = 26
f(54) = 9
f(55) = 20
f(56) = 12
f(57) = 18
f(58) = 14
f(59) = 29
f(60) = 8
f(61) = 30
f(62) = 15
f(63) = 18
f(64) = 16
f(65) = 24
f(66) = 10
f(67) = 33
f(68) = 16
f(69) = 22
f(70) = 12
f(71) = 35
f(72) = 12
f(73) = 36
f(74) = 18
f(75) = 20
f(76) = 18
f(77) = 30
f(78) = 12
f(79) = 39
f(80) = 16
f(81) = 27
f(82) = 20
f(83) = 41
f(84) = 12
f(85) = 32
f(86) = 21
f(87) = 28
f(88) = 20
f(89) = 44
f(90) = 12
f(91) = 36
f(92) = 22
f(93) = 30
f(94) = 23
f(95) = 36
f(96) = 16
f(97) = 48
f(98) = 21
f(99) = 30
f(100) = 20

Unique list of m's with no solution for n (1, 100): 
7,13,17,19,25.....

Smallest m = 7

1 2	`Unique list of m's with no solution for n (1, >1000): [7, 13, 17, 19, 25, 31, 34, 37, 38, 43, 45, 46, 47, 49, 57, 58, 59, 61, 62, 71, 73, 76, 77, 79, 85, 87, 91, 93, 94, 97, 101......]`

@Michael Fitzgerald , we really liked your comment, and have converted it into a solution. If you subscribe to this solution, you will receive notifications about future comments.

Brilliant Mathematics Staff - 3 years, 3 months ago

Romain Bouchard
Feb 19, 2018

From $n>1$ , $f(n)$ can be understood as the number of ordered partitions of $n$ between two coprime integers ( $8 = 1+7 = 3+5$ ) also known as the half- totient $\frac{\Phi(n)}{2}$ .

We can verify that $f(3)=1$ , $f(5)=2$ , $f(7)=3$ , $f(15)=4$ , $f(11)=5$ , $f(13)=6$ .

However, there is no integer $n$ that can be split into $14$ partitions ( $7$ ordered partitions) between two coprimes integers.

@Romain Bouchard Could you explain why there is no integer n such that $\phi(n)=14$ ?

John Frank - 3 years, 3 months ago

Sure. Suppose there is an integer $n$ such that $\phi(n)=14$ :

If the prime number $p$ is a divisor of $n$ , then $p-1∣\phi(n)$ by definition of $\phi$ $\Rightarrow p-1|14$ .
Since the divisors of $14$ are $1, 2, 7$ and $14$ , then $p=2$ or $p=3$ .
Thus, $n=2^a3^b$ and $\phi(n) = 2^j3^k$ .
However, $7$ can never be a factor of $2^j3^k$ , hence there is no integer $n$ such that $\phi(n)=14$ .

Romain Bouchard - 3 years, 3 months ago

These numbers are known as non-totients. The sequence of such $2n$ is given in OEIS 5277 .
There isn't a complete classification of these numbers as yet.

Calvin Lin Staff - 3 years, 3 months ago

Yannick Kirschhoffer
Mar 4, 2018

A more concise Python implementation:

from math import gcd


def f(n):
    result = []

    for p in range(1, n + 1):
        for q in range(p, n + 1):
            if (p + q == n) and (0 < p / q < 1) and (gcd(p, q) == 1):
                result.append((p, q))

    return len(result)


results = set([f(n) for n in range(1, 100)])

print(results)

Will display:

1	`{0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 32, 33, 35, 36, 39, 41, 44, 48}`

See original code on GitHub

Ariijit Dey
Mar 3, 2018

I got it!!! Its the Carmhichael's function $\frac{1}{2}$ $\phi(n)$ . since $\phi(n)$ cannot be 14; so the former cannot be 7

Marko Skakun
Mar 1, 2018

Simple python code for finding m's for integers from 1 to 100, just check for first missing integer in list

from fractions import gcd
list = []
for i in range(1, 100):
  s = 0
  for p in range(1, i/2+1):
    q = i-p
    if q>p and gcd(p,q)==1:
      s+=1
  list.append(s)
list.sort()
print list

Rational and Irreducible

The answer is 7.

6 solutions

0 pending reports