4
$\begingroup$

If $n$ is in the range of the Euler totient function, certain multiples of $n$ are likewise guaranteed to be totient values. The simplest nontrivial example of this is that, if $n$ is in the range of totient, so is $2n$:
Write $n = \phi(k)$.
If $k$ is odd, then $2n = \phi(4k)$. If $k$ is even, then $2n = \phi(2k)$.
More generally, for all positive integers $m \leq 27$, I can determine whether or not the range of totient is carried to itself by multiplication by $m$:
$m=1$: This trivially preserves being a totient value.
If $m \geq 3$ and $m$ is odd, multiplication by $m$ does not preserve being a totient value, since $1 = \phi(1)$ but $m$ is not in the range of $\phi$.
$m=2$: See above. Note that since multiplication by $2$ preserves being a totient value, so does multiplication by $4$, $8$, or $16$.
$m=6$: Multiplication by $6$ preserves being a totient value:
As before, write $n = \phi(k)$.
If $3 \nmid k$, $6n = \phi(9k)$.
If $3 \mid k$, $3n = \phi(3k)$. Then, since $3n$ is a totient value, so is $6n$.
$m=10$: $110 = \phi(11^{2})$ but $110 \cdot 10 = 1100$ is not in the range of $\phi$.
$m=12$: Multiplication by $6$ and $2$ will carry totient values to totient values, so multiplication by $12$ will too.
$m=14$: $14$ is not in the range of $\phi$, so multiplication by $14$ does not carry $1$ to a totient value.
$m=18$: Multiplication by $18$ preserves being a totient value:
As before, write $n = \phi(k)$.
If $3 \nmid k$, $18n = \phi(27k)$.
If $3 \mid k$, $9n = \phi(9k)$. Then, since $9n$ is a totient value, so is $18n$.
$m=20$: Multiplication by $20$ preserves being a totient value.
As before, write $n = \phi(k)$.
If $5 \nmid k$, $20n = \phi(25k)$.
If $5 \mid k$, $5n = \phi(5k)$. Then, since $5n$ is a totient value, so is $20n$.
$m=22$: $22 = \phi(23)$ but $22 \cdot 22 =484$ is not in the range of $\phi$.
$m=24$: Multiplication by $12$ and $2$ will carry totient values to totient values, so multiplication by $24$ will too.
$m=26$: $1$ is in the range of $\phi$ but $26$ is not.

So my question is: Does multiplication by $28$ always carry totient values to totient values?
I have tried submitting a sequence to the OEIS consisting of positive integers multiplication by which preserves being a totient value, but I have not had enough terms for the sequence (or an algorithm for determining membership in the sequence). (Should I mention what the sequence number would be if it were approved? I also don't think extending the sequence by this single term would make it admissible, but it's good to have this problem sized up by people who can devote more time to it than I can.)

$\endgroup$
5
  • $\begingroup$ Presumably you've experimentally looked for counterexamples to $28\phi(\mathbb Z_{> 0}) \subseteq \phi(\mathbb Z_{> 0})$. How far did you go? $\endgroup$
    – LSpice
    Commented Aug 2, 2018 at 13:31
  • $\begingroup$ oeis.org/A002202/b002202.txt goes up to 47196, and for every value $k$ up to 47196/28, $28k$ occurs in the list as well. $\endgroup$
    – Glorfindel
    Commented Aug 2, 2018 at 13:35
  • $\begingroup$ That is not how I approached it. I tried analyzing the factorization of k, but that becomes messy. (This gave me the impression that computer power is not sufficient to make such a direct approach as ^that fruitful, though maybe I was being too easily discouraged.) $\endgroup$ Commented Aug 2, 2018 at 14:29
  • $\begingroup$ we have $28\phi(i) = \phi(ki)$ for all if $k$ is some number with $\phi(k)=28$ and $i$ and $k$ coprime, right? $\endgroup$ Commented Aug 2, 2018 at 14:40
  • $\begingroup$ Yes, but what if the i is already a multiple of $29$? Then the only numbers that make $\phi$ equal to $28$ are $29$ and $58$, so they're both out. $\endgroup$ Commented Aug 2, 2018 at 14:44

1 Answer 1

10
$\begingroup$

The answer is: no.

Here is the smallest counterexample: take $n = 29\cdot7645373 = 221715817 = 29\cdot 197^3$.

Then $\phi(n) = 212983792$ and $28\cdot\phi(n)=5963546176$, but the last number is not totient of any number.

I found this using the following pari one-liner:

? for (i=0,10000000, if(!istotient(28*eulerphi(29*i)), print(i)))
7645373

Edit: Looking a bit further, there are quite a few counterexamples of the form $n=29\cdot197^3\cdot i$

? for (i=1, +oo, if(!istotient(28*eulerphi(29*197^3*i)), print1(i); print1(",")))
1,2,3,4,6,7517,15034,18059,22551,28019,30068,30983,36118,45102,56038,61966,65267,67427,67499,71387,84057,84947,90677,92949,97187,112076,115469,123932,127487,130534,130787,134854,134998,142774,168114,169067,169894,181354,185898,191579,194374,195801,202281,214161,218627,227519,230189,230938,233939,239843,247847,252029,253367,254841,254974,261068,261574,262643,269708,272031,285548,289937,291561,294059,297707,330587,338134,339788,339827,347003,349343,350159,362708,381917,383158,387503,388748,391602,392361,404562,405683,427247,428322,437254,440039,447179,454907,455038,460378,467783,467878,475367,479686,489197,495694,504058,506734,507201,509682,514247,523148,525286,544062,546719,548837,548903,564797,569813,574737,579287,579874,583122,588118,595414,597383,608117,628379,635939,644597,647579,654527,655881,661174,664019,676268,679654,682557,690567,694006,697259,698686,700318,701817,714827,718139,723287,739163,743541,748019,750719,760101,763013,763834,766316,775006,776267,781307,784722,787929,800399,804179,811366,817319,829847,832787,847163,850727,854494,863887,874508,877403,878987,880078,880799,882083,889589,894358,901997,909814,910076,920756,935566,935756,950734,962747,974837,978203,978394,979919,980327,981287,989123,991388,991761,1013468,1014402,1017923,1019481,1028494,1030307,1036307,1041009,1048029,1050572,1053293,1053407,1070039,1082717,1093438,1097674,1097806,1119299,1129594,1138637,1139626

If you are looking for even larger $n$, one can take numbers of the form $n=29\cdot 197^14\cdot i$ for $i\in\{1,2,116387,232774,...\}$

These small cases make it plausible, that there are infinitely many counterexamples. Can you find an infinite family? Are there counterexamples, that cannot be divided by $197^3$?

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .