Smallest Even Integer whose Euler Phi Value is not the Euler Phi Value of an Odd Integer

From ProofWiki
Jump to navigation Jump to search

Theorem

The smallest even integer whose Euler $\phi$ value is shared by no odd integer is $33 \, 817 \, 088$.


Proof

We have:

\(\ds \map \phi {33 \, 817 \, 088}\) \(=\) \(\ds 16 \, 842 \, 752\) $\phi$ of $33 \, 817 \, 088$
\(\ds \) \(=\) \(\ds 2^{16} \times 257\)

Consider the equation:

$(1): \quad \map \phi x = 2^{16} \times 257$

Let $p$ be an odd prime factor of $x$.

Then as Euler Phi Function is Multiplicative, we have:

$p - 1 \divides p^{k - 1} \paren{p - 1} = \map \phi {p^k} \divides \map \phi x$

where $k$ is the highest power of $p$ dividing $x$.

Therefore, by considering divisors of $\map \phi x$, either:

$p - 1 = 2^j$ for some $j \in \Z$ such that $1 \le j \le 16$

which corresponds to the Fermat primes, or:

$p - 1 = 2^j \times 257$ for some $j \in \Z$ such that $1 \le j \le 16$


But $2^j \times 257 + 1$ is composite for $1 \le j \le 16$:

\(\ds j = 1: \, \) \(\ds 2^1 \times 257 + 1\) \(=\) \(\ds 515\) \(\ds = 5 \times 103\)
\(\ds j = 2: \, \) \(\ds 2^2 \times 257 + 1\) \(=\) \(\ds 1029\) \(\ds = 3 \times 7^3\)
\(\ds j = 3: \, \) \(\ds 2^3 \times 257 + 1\) \(=\) \(\ds 2057\) \(\ds = 11^2 \times 17\)
\(\ds j = 4: \, \) \(\ds 2^4 \times 257 + 1\) \(=\) \(\ds 4113\) \(\ds = 3^2 \times 457\)
\(\ds j = 5: \, \) \(\ds 2^5 \times 257 + 1\) \(=\) \(\ds 8225\) \(\ds = 5^2 \times 7 \times 47\)
\(\ds j = 6: \, \) \(\ds 2^6 \times 257 + 1\) \(=\) \(\ds 16 \, 449\) \(\ds = 3 \times 5483\)
\(\ds j = 7: \, \) \(\ds 2^7 \times 257 + 1\) \(=\) \(\ds 32 \, 897\) \(\ds = 67 \times 491\)
\(\ds j = 8: \, \) \(\ds 2^8 \times 257 + 1\) \(=\) \(\ds 65 \, 793\) \(\ds = 3 \times 7 \times 13 \times 241\)
\(\ds j = 9: \, \) \(\ds 2^9 \times 257 + 1\) \(=\) \(\ds 131 \, 585\) \(\ds = 5 \times 26 \, 317\)
\(\ds j = 10: \, \) \(\ds 2^{10} \times 257 + 1\) \(=\) \(\ds 263 \, 169\) \(\ds = 3^6 \times 19^2\)
\(\ds j = 11: \, \) \(\ds 2^{11} \times 257 + 1\) \(=\) \(\ds 526 \, 337\) \(\ds = 7 \times 17 \times 4423\)
\(\ds j = 12: \, \) \(\ds 2^{12} \times 257 + 1\) \(=\) \(\ds 1 \, 052 \, 673\) \(\ds = 3 \times 350 \, 891\)
\(\ds j = 13: \, \) \(\ds 2^{13} \times 257 + 1\) \(=\) \(\ds 2 \, 105 \, 345\) \(\ds = 5 \times 11 \times 101 \times 379\)
\(\ds j = 14: \, \) \(\ds 2^{14} \times 257 + 1\) \(=\) \(\ds 4 \, 210 \, 689\) \(\ds = 3 \times 7 \times 43 \times 4663\)
\(\ds j = 15: \, \) \(\ds 2^{15} \times 257 + 1\) \(=\) \(\ds 8 \, 421 \, 377\) \(\ds = 1123 \times 7499\)
\(\ds j = 16: \, \) \(\ds 2^{16} \times 257 + 1\) \(=\) \(\ds 16 \, 842 \, 753\) \(\ds = 3^2 \times 1 871417\)

So the only possible odd prime factors of $x$ are the Fermat primes not exceeding $2^{16} + 1$:

$3, 5, 17, 257, 65 \, 537$

such that:

$257$ occurs with multiplicity $2$, since we need $257$ to be a factor of $\map \phi x$ but not $257^2$;
all other prime factors occurs with multiplicity $1$, since we do not want these primes to be factors of $\map \phi x$.

As we have:

\(\ds \map \phi {257^2 \times 65 \, 537}\) \(=\) \(\ds 257 \times 256 \times 2^{16}\)
\(\ds \) \(>\) \(\ds 2^{16} \times 257\)

it follows that $257$ and $65 \, 537$ cannot appear together.

We can now write:

$x = 2^y \times 3^{\epsilon_0} \times 5^{\epsilon_1} \times 17^{\epsilon_2} \times 257^2$

where each $\epsilon_i = 0$ or $1$.


Aiming for a contradiction, suppose $x$ is odd, that is, $y = 0$.

We have that:

\(\ds \map \phi x\) \(=\) \(\ds \map \phi {3^{\epsilon_0} \times 5^{\epsilon_1} \times 17^{\epsilon_2} \times 257^2}\)
\(\ds \) \(=\) \(\ds 2^{\epsilon_0} \times 4^{\epsilon_1} \times 16^{\epsilon_2} \times 256 \times 257\) as $\epsilon_i = 0$ or $1$
\(\ds \) \(=\) \(\ds 2^{\epsilon_0 + 2 \epsilon_1 + 4 \epsilon_2 + 8} \times 257\)
\(\ds \) \(\le\) \(\ds 2^{1 + 2 + 4 + 8} \times 257\) as $\epsilon_i = 0$ or $1$
\(\ds \) \(<\) \(\ds 2^{16} \times 257\)
\(\ds \) \(=\) \(\ds \map \phi x\)

which is a contradiction.

Thus there can be no odd integer $x$ satisfying $(1)$, that is, $y \ge 1$.


Note that:

\(\ds \map \phi {2^y \times 3^{\epsilon_0} \times 5^{\epsilon_1} \times 17^{\epsilon_2} \times 257^2}\) \(=\) \(\ds 2^{y - 1} \times 2^{\epsilon_0} \times 4^{\epsilon_1} \times 16^{\epsilon_2} \times 256 \times 257\) as $\epsilon_i = 0$ or $1$
\(\ds \) \(=\) \(\ds 2^{y - 1 + \epsilon_0 + 2 \epsilon_1 + 4 \epsilon_2 + 8} \times 257\)
\(\ds \) \(=\) \(\ds 2^{16} \times 257\)
\(\ds \leadsto \ \ \) \(\ds y - 1 + \epsilon_0 + 2 \epsilon_1 + 4 \epsilon_2 + 8\) \(=\) \(\ds 16\)
\(\ds \leadsto \ \ \) \(\ds y\) \(=\) \(\ds 9 - \epsilon_0 - 2 \epsilon_1 - 4 \epsilon_2\)

Therefore even solutions to $(1)$ are of the form:

$x = 2^{9 - \epsilon_0 - 2 \epsilon_1 - 4 \epsilon_2} \times 3^{\epsilon_0} \times 5^{\epsilon_1} \times 17^{\epsilon_2} \times 257^2$

Since each of:

$2^{-1} \times 3^1$
$2^{-2} \times 5^1$
$2^{-4} \times 17^1$

are greater than $1$, taking $\epsilon_i = 0$ for $i = 0, 1, 2$ would result in the smallest even integer satisfying $(1)$, that is:

$x = 2^9 \times 257^2 = 33 \, 817 \, 088$


It can be established by computer that $33 \, 817 \, 088$ is the smallest even integer whose Euler $\phi$ value is shared by no odd integer.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Smallest_Even_Integer_whose_Euler_Phi_Value_is_not_the_Euler_Phi_Value_of_an_Odd_Integer&oldid=689197"