Prove $a^k\equiv 1 \pmod k$ has no solution for infinitely many even integers k

106 Views Asked by At

Prove that there are infinitely many EVEN positive integers $k$ such that for each of those $k$, the equation $\varphi(n) = k$ has no solution in positive integers $n$.

I believe there might be a way to approach this using Euler's Theorem where one proves $a^k\equiv 1 \pmod k$ has no solution for infinitely many even numbers.

1

There are 1 best solutions below

0
On BEST ANSWER

Note: This is answer to your "actual" question and not the title question.

Claim: There is no positive integer $n$ such that $\varphi(n)=2p$, where $p$ is a prime and $2p+1$ is composite.

Proof

Suppose there is an $n$ such that $\varphi(n)=2p$. Let $q$ be a prime such that $q | n$, then by definition $q-1 | \varphi(n)$. This implies $q-1 | 2p$. With $p$ being a prime, the only positive divisors of $2p$ are $\{1,2,p,2p\}$. Thus $q-1 \in \{1,2,p,2p\}$.

Observe that $q-1 \neq p,2p$ because if it were then $q=p+1$ and $q=2p+1$ respectively. In both cases, from the conditions given ($p > 5$ and $2p+1$ is composite) $q$ cannot be a prime. Thus the only possibilities left are $q=2$ or $q=3$. This means should such an $n$ exist, it must of the form $n=2^a \cdot 3^b$, where $a,b \geq 0$. But then $$\varphi(n)= \begin{cases} 2^{a} \cdot 3^{b-1} & \text{ if } a,b \geq 1\\ 2^{a-1} & \text{ if } a \geq 1, b=0\\ 2 \cdot 3^{a-1} & \text{ if } a=0, b \geq 1\\ 1 & \text{ if } \text{otherwise} \end{cases} $$ So for $\varphi(n)=2p$, we will have that $p \in \{2,3\}$. But this cannot happen as $2p+1$ is not composite in both scenarios. Thus such an $n$ cannot exist.