Tuesday 14 February 2023

Divisibility of Integers by their Totients

I got to thinking about the conditions for a number to be divisible by its totient. It didn't take too long to see the pattern. Figure 1 shows the results for numbers up to 1024.


Figure 1: permalink

Clearly condition is that the numbers must by of the form \(2^p3^q\) where \(p>0\) and \(q \geq 0\). There are only 35 numbers in this range and, if we extend the range to 10 million, there are still only 178 numbers that satisfy.

These numbers form OEIS A007694:


 A007694

Numbers \(k\) such that \( \phi(k) \) divides \(k\).   
          

The initial members of the sequence are:

1, 2, 4, 6, 8, 12, 16, 18, 24, 32, 36, 48, 54, 64, 72, 96, 108, 128, 144, 162, 192, 216, 256, 288, 324, 384, 432, 486, 512, 576, 648, 768, 864, 972, 1024, 1152, 1296, 1458, 1536, 1728, 1944, 2048, 2304, 2592, 2916, 3072, 3456, 3888, 4096, 4374, 4608, 5184, 5832, 6144, 6912, 7776, 8192, 8748, 9216

The numbers must be even, that is they must contain a power of 2. If the numbers are only powers of 3 then the dividend is 1.5. Figure 2 shows the results in the range up to one million. All numbers are of the form \(3^p\) where \(p>0\).


Figure 2: permalink

What sort of numbers will produce a dividend of 2.5? Well, as it turns out, numbers of the form \(2^p5^q\) where \(p>1\) and \(q>1\). See Figure 3 for the numbers in the range up to one thousand.


Figure 3: permalink

A dividend of 3.5 is produced by numbers of the from \(2^p3^q7^r \) where \(p>0\), \(q>0\) and \(r>0\). See Figure 4 for the numbers in the range up to one thousand.


Figure 4: permalink

Numbers involving 11 as a factor appear if the dividend is 2.2 where numbers are of the form \(2^p11^q\) where \(p>0\) and \(q>0\). See Figure 5 where the range is up to ten thousand.


Figure 5: permalink

Numbers of the from \(2^p11^q23^q\) with \(p>0\), \(q>0\) and \(r>0\) produce a dividend of 2.3. See Figure 6 where the range is up to 100,000.


Figure 6: permalink

Numbers of the form \(2^p3^q31^r\) where \(p>0\), \(q>0\) and \(r>0\) produce a dividend of 3.1. Figure 7 shows the range up to ten thousand.


Figure 7: permalink

Numbers of the form \(2^p3^q11^r\) where \(p>0\), \(q>0\) and \(r>0\) produce a dividend of 3.3. See Figure 8 for numbers in the range up to one thousand.


Figure 8: permalink

More numbers emerge when we consider dividends like 3.25 and 3.75 but I'll stop there even though there is clearly room for further study of this topic. The following is a summary of what I found so far:
  • \( \dfrac{n}{\phi(n)}=k\) where \(k>0\) if numbers of form \(2^p3^q\) with \(p>0\) and \(q \geq 0\)
  • \( \dfrac{n}{\phi(n)}=1.5\) if numbers of form  \(3^p\) with \(p>0\)
  • \( \dfrac{n}{\phi(n)}=2.2\) if numbers of form  \(2^p11^q\) where \(p>0\) and \(q>0\)
  • \( \dfrac{n}{\phi(n)}=2.3\) if numbers of form \(2^p11^q23^q\) with \(p>0\), \(q>0\) and \(r>0\)
  • \( \dfrac{n}{\phi(n)}=2.5\) if numbers of form \(2^p5^q\) with \(p>0\) and \(q>0\)
  • \( \dfrac{n}{\phi(n)}=3.1\) if numbers of form \(2^p3^q31^r\) where \(p>0\), \(q>0\) and \(r>0\)
  • \( \dfrac{n}{\phi(n)}=3.3\) if numbers of form \(2^p3^q11^r\) where \(p>0\), \(q>0\) and \(r>0\)
  • \( \dfrac{n}{\phi(n)}=3.5\) if numbers of form \(2^p3^q7^r \) with \(p>0\), \(q>0\) and \(r>0\)

No comments:

Post a Comment