Crikey Math

Having fun exploring mathematics

  • Home
  • About
  • Blog
  • Contribute
en English
af Afrikaanssq Albanianam Amharicar Arabichy Armenianaz Azerbaijanieu Basquebe Belarusianbn Bengalibs Bosnianbg Bulgarianca Catalanceb Cebuanony Chichewazh-CN Chinese (Simplified)zh-TW Chinese (Traditional)co Corsicanhr Croatiancs Czechda Danishnl Dutchen Englisheo Esperantoet Estoniantl Filipinofi Finnishfr Frenchfy Frisiangl Galicianka Georgiande Germanel Greekgu Gujaratiht Haitian Creoleha Hausahaw Hawaiianiw Hebrewhi Hindihmn Hmonghu Hungarianis Icelandicig Igboid Indonesianga Irishit Italianja Japanesejw Javanesekn Kannadakk Kazakhkm Khmerko Koreanku Kurdish (Kurmanji)ky Kyrgyzlo Laola Latinlv Latvianlt Lithuanianlb Luxembourgishmk Macedonianmg Malagasyms Malayml Malayalammt Maltesemi Maorimr Marathimn Mongolianmy Myanmar (Burmese)ne Nepalino Norwegianps Pashtofa Persianpl Polishpt Portuguesepa Punjabiro Romanianru Russiansm Samoangd Scottish Gaelicsr Serbianst Sesothosn Shonasd Sindhisi Sinhalask Slovaksl Slovenianso Somalies Spanishsu Sudanesesw Swahilisv Swedishtg Tajikta Tamilte Teluguth Thaitr Turkishuk Ukrainianur Urduuz Uzbekvi Vietnamesecy Welshxh Xhosayi Yiddishyo Yorubazu Zulu

Some comments on fractions of integers less than and coprime to n

January 3, 2018 By Gary Ernest Davis

James Tanton (@jamestanton) asked the following question on Twitter (December 31, 2017):

“If all of the numbers 1, 2, …, n-1 are coprime to n (share only the factor 1 with n), then n must be prime. Is there an n with precisely half of the numbers 1,2,…,n-1 coprime to n? One with precisely a third of them coprime to n?”

There is a well-known name for the number of positive integers less than and coprime to n: this is Euler’s totient function, denoted \phi(n) .

A pretty mindless computation indicates there’s not likely to be any positive integers k such that a fraction 1/k of the numbers 1,2,\ldots, n-1 are coprime with n.

The Mathematica code below was aborted at  n = 1,038,898,229 without finding any such k:

n = 2;
While[IntegerQ[(n – 1)/EulerPhi[n]] == False, n++]
n

So why might this be so?


Euler’s product formula for the totient function is:

\displaystyle\phi(n)=n\prod_{p|n, p \textrm{ prime}}(1-\frac{1}{p})

so to say, for example, that

\frac{\phi(n)}{n-1}=\frac{1}{3}

is to say that

\displaystyle3\prod_{p|n}(1-\frac{1}{p})=1-\frac{1}{n}

While it’s commonly the case that

\displaystyle3\prod_{p|n}(1-\frac{1}{p})>1-\frac{1}{n}

it is not universally so. For example if n is the product of the primes 2, 3, 71, 491, 1031, 1489, 1657, 1949, 2269, 2381, 3613, 4079, 5743, 5807, 6131, 6257, 6637, 6709, 7207, 7433 then

\displaystyle3\prod_{p|n}(1-\frac{1}{p}) < 1-\frac{1}{n}

So, at least from the perspective of Euler’s totient formula, the question even of whether there is an n for which

\frac{\phi(n)}{n-1}=\frac{1}{3}

seems to be a little subtle.


When n=p_1p_2\ldots p_k is a product of distinct primes  p_1,p_2,\ldots,p_k then

\frac{\phi(n)}{n-1}=\frac{1}{3}

is equivalent to

3(p_1-1)(p_2-1)\ldots (p_k-1)= p_1p_2\ldots p_k - 1

We can see how this isn’t possible for a product of 2 primes (i.e. k=2):

if 3(p_1-1)(p_2-1)= p_1p_2 - 1 then

2p_1p_2 -3(p_1+p_2) + 4 = 0

We can write p_2=p_1+d where d\neq 0 because p_1\neq p_2.

Then,

2 p_1^2 +(2d-6)p_1 +4-3d=0

which means

p_1 =(3 - d + \sqrt{1 + d^2})/2

which is not possible since 1+d^2 is not a square.

For a product of 3 distinct primes p_1,p_2,p_3 we can do something similar, writing p_2=p_1+d_1, p_3=p_1+d_2 and end up with a cubic polynomial in p_1 with coefficients involving d_1, d_2. As we get a larger collection of primes we get polynomials, with integer coefficients, in p_1 of higher degree (for which the rational roots test doesn’t seem to help).

 


We can also see how \frac{\phi(n)}{n-1}=\frac{1}{3} is not possible when n = p^k is a prime power:

from \frac{\phi(n)}{n-1}=\frac{1}{3} we get 2p^k-3p^{k-1}+1=0 and the rational roots test tells us that the only integer solution is p=1.


 Maybe more is clear to a number theorist. At this point however, I am stumped.

http://www.crikeymath.com/wp-content/uploads/2017/09/crikey.wav

 

Filed Under: Uncategorized

Recent Posts

  • Does the DNA test say guilty or not guilty?
  • The Turtleback Diagram for Conditional Probability
  • Numbers that, base 2, are blindingly obviously divisible by 3
  • A mysterious sequence of 1s and 2s
  • Does one have to be a genius to do mathematics? Neither necessary nor sufficient.
  • Alexander Bogomolny
  • Binary disjoints of an integer
  • A cycle of length 5 for iterated squaring modulo a prime
  • The diagonal of the Wythoff array
  • Leonardo Bigollo, accountant, son of Bill Bonacci

Archives

Copyright © 2023 · Dynamik Website Builder on Genesis Framework · WordPress · Log in