# How to show that there is no odd $n$ bigger than 100 such that the group $U(n)$ will contain $2^n$ number of elements?

Consider $U(n):=\{1\leq r\leq n: (r, n)=1\}$. Under multiplication modulo $n$ it forms an abelian group. Its order will be $\varphi(n)$ i.e. $\varphi(n)=|U(n)|$.

Assume that $n\geq 100$. Then my question is : does there exists any odd natural number $m_o$ such that the group $U(n)$ will have the order $2^n$ ? The reason I have chosen $n\geq 100$ is that : I have already checked the result below 100 and the answer I have obtained so far is NO if $33\leq n\leq 100$. No need to care about $n\leq 33$. I think the result is still NO if we go beyond 100.

But the question is : how can I show no such odd $m_o$ would exists ?

What I have approached is the following: Since $m_o$ is odd so we can write $$m_o=\prod\limits_{i=1}^r p_i^{a_i}$$ where $p_i$ are odd primes and $a_i$ are positive integers. Then we must have $$U(m_o)\simeq U(p_1^{a_1})\times \cdots \times U(p_r^{a_r})$$ where $\times$ denotes the external direct product of groups. I don't know if we can create some contradiction over here.

Also note that , the question is equivalent to say that if $m_o$ is one such odd number then there will be $2^n$ number of positive integers less than $m_o$ and relatively prime to $n$. We have to show no such $m_o$ is possible to find after 100.

in this way also no contradiction i am able to get.

• Are you sure you want the same $n$ in $U(n)$ and in $2^n$? – Derek Holt Oct 27 '14 at 5:26
• Well $2^n > n > |U(n)|$ for all $n > 1$. – Derek Holt Oct 27 '14 at 5:41

As you did, write $m = p_1^{a_1} \cdots p_k^{a_k}$ (with $a_i>0$). You know that $$\varphi(m) = \prod_{i=1}^k \left((p_i-1)\cdot p_i^{a_i-1}\right)$$

Now assume $\varphi(m) =2^n$. Then each of the terms in the above product must be powers of 2. In particular, $p_i^{a_i-1}$ must be a power of $2$, so $a_i = 1$ if $p_i>2$, and $p_i-1$ must be a power of $2$; so $2^j +1 = p_i$ for some $j$. Here's where we run into trouble: we have no idea whether or not there are infinitely many such primes $p_i$! Primes of this form are necessarily Fermat primes.

There are two known Fermat primes greater than 100: $257$ and $65537$. If $m$ is odd, it must be a product of Fermat primes; the only known such odd numbers with $\varphi(m)= 2^n$ are $3, 5, 17, 257, 65537$ and products of these. It is not known if these are the only ones, or even if there are only finitely many Fermat primes. So the answer is "it isn't known whether or not there are odd $m$ such that $\varphi(m)=2^n$ for $n>100$".

(Note that $\varphi(3\cdot 5 \cdot 17 \cdot 257 \cdot 65537) = 2^{31}$; this is the highest known $2^n$ achievable as $\varphi(m)$. If anything larger is possible, it's enormous.)

You want positive integers $n$ such that $\varphi(n)$ is a power of $2$. But if $n=p_1^{a_1}\cdots p_m^{a_m}$, then $\varphi(n)=\displaystyle\prod_{i=1}^m (p_i^{a_i}-p_1^{a_1-1})$.

Therefore, the only primes you can have are $2$ and those such that $p_i-1$ is a power of $2$. The only such primes which are known are $3, 5, 17, 257, 65537$.

• $\varphi(5) = 4$ – user98602 Oct 27 '14 at 5:17
• @Nishant what I want: (1) $n$ is odd, (2) $n$ is bigger than 100. Not less than 100. – Anjan3 Oct 27 '14 at 5:18
• Derek Holt please note than $256=2^8$ which means $n=8$. I asked $n\geq 100$. – Anjan3 Oct 27 '14 at 5:21
• Sorry about that...that's what I get for doing math this late. – Nishant Oct 27 '14 at 5:21