For the give functions in $\mathbb{N}$: (a) Euler's $\phi$ function ($\phi(n)$- the number of natural numbers smaller than $n$ and coprime with $n$); (b) the $\sigma$ function such that the $\sigma(n)$ is the sum of natural divisors of $n$. solve the equation $\phi(\sigma(2^x))=2^x$.
Problem
Source:
Tags: function, modular arithmetic, Euler, number theory unsolved, number theory
05.06.2010 02:37
Not a terribly rigorous (more heuristic) argument but perhaps someone could make it more rigorous (at least it's a start): Note the trivial solution $x = 0$. Now suppose that $x > 0$. $ \varphi ( \sigma (2^x) ) = \varphi (2^{x+1} -1) = 2^x $ Now let $ \displaystyle\prod_{i=1}^np_i^{a_i}$ be a prime decomposition of $2^{x+1} -1$, where each $p_i$ is odd, and $ p_i < p_{i+1} \ \forall i \in \{ 1, 2, ... , n-1 \}$. Thus: $2^x = \varphi (\displaystyle\prod_{i=1}^np_i^{a_i}) = \displaystyle\prod_{i=1}^n p_i^{a_i-1} (p_i-1) $ So we must have that $ a_i = 1 \ \forall i $ and also, $ p_i - 1 = 2^{m_i} $, for some $m_i \in \mathbb{N}$, with $\displaystyle\sum_{i=1}^n m_i = x $. Indeed, each $p_i$ is a Fermat prime, and hence $m_i = 2^{k_i}$ for some non-negative integer $k_i$. Now, for each $p_i$, $2^{x+1} \equiv 0 \pmod{p_i} \implies p_i-1 | x+1 \iff 2^{2^{k_i}} |x+1$, so $x+1$ has powers of 2 dividing it - its binary representation will end in 'a lot' of zeros. On the other hand, $2^x = \displaystyle\prod_{i=1}^n (p_i-1) \implies x = 2^{k_1} + 2^{k_2} + \cdots + 2^{k_n}$ is a binary representation of x, and so has 'lots' of 1s in its representation. It is now clear that $x$ must be a Mersenne number, and thus has a binary representation with all 1s. Each 1 corresponds to a Fermat prime dividing $2^{x+1}-1$, and thus they must be consecutive Fermat primes, starting from the first. Thus $2^{x+1}-1 \in \{ 3, 3 \times 5, 3 \times 5 \times 17, 3 \times 5 \times \17 \times 257, 3 \times 5 \times 17 \times 257 \times 65537 \}$ These correspond to solutions $x \in \{ 1, 3, 7, 15, 31\} $ Thus the solutions are $x \in \{ 0, 1, 3, 7, 15, 31 \} $
05.06.2010 02:45
ridgers wrote: For the give functions in $\mathbb{N}$: (a) Euler's $\phi$ function ($\phi(n)$- the number of natural numbers smaller than $n$ and coprime with $n$); (b) the $\sigma$ function such that the $\sigma(n)$ is the sum of natural divisors of $n$. solve the equation $\phi(\sigma(2^x))=2^x$. indeed $n=1$ is obviously solution now assume that $n>1$ thus The equation is equivalent to $\phi(2^{n+1}-1)=2^n$ but due to Euler Theorem $2^{n+1}-1 \mid 2^{\phi(2^{n+1}-1)}-1$ which give $n+1 \mid \phi(2^{n+1}-1)$ because $(2^a-1,2^b-1)=2^{(a,b)}-1$ or from the equation we get $n+1\mid 2^n$ and so $n+1$ is a power of $2$ so let $n=2^m-1$ Thus the equation is equivalent to $\phi(2^{2^m}-1)=2^{2^m-1}$ but $2^{2^m}-1=(2+1)(4+1)..(2^{2^{m-1}}+1)$ yields that $\phi(2^{2^m}-1)=\prod \phi(2^{2^k}+1)$ but using the fact that $\phi(n) \le n-1$ whith equality if and only if $n$ is prime we get that $\prod \phi(2^{2^k}+1) \le \prod 2^{2^k}=2^{2^m-1}$ hence all the numbers $2^{2^k}+1$ are primes and this is not true because The sequence of Fermat's numbers in no more prime for some positive integer $\lambda$ hence it's easy to check the solutions less than $\lambda$
05.11.2011 07:55
it suffices to solve $\pi (2^{x+1}-1)=2^x$ hence all prime divisors of $2^{x+1}-1$ are in the form $2^k+1$ and square free mod 4,we get a divisor 3.hence $2|x+1$. since $2^{x+1}-1=(2^{\frac{x+1}{2}}-1)(2^{\frac{x+1}{2}}+1)$ if $4|x+1$ doesn't hold then $2^{\frac{x+1}{2}}-1$ has a 4k+3 divisor differ from 3,contradiction! hence $4|x+1$ analagously,we can get $8|x+1,16|x+1,...$ hence $x+1$ is a power of 2. because $2^{2^5}=F_5$is not prime,we get $x=1,3,7,15$.
05.11.2011 09:02
It can easily be determined only Fermat primes satisfy this equation... however it is an open problem as to if there are infinitely any Fermat primes beyond $2^{2^4} + 1$, so this problem can't really be solved.
19.05.2012 21:48
The equation rewrites as $\phi (2^{x+1}-1)=2^x$. Let now $2^{x+1}-1=\prod _{i=1} ^k p_i ^{\alpha _i}$ the factorization of $2^{x+1}-1$; since $\phi$ is multiplicative, $2^x=\phi(2^{x+1}-1)=\phi \left ( \prod _{i=1} ^k p_i ^{\alpha _i} \right )= \prod _{i=1} ^k \phi (p_i ^{\alpha _i}) =\prod _{i=1} ^k p_i ^{\alpha _i-1}(p_i-1)$; then since the $p_i$'s are odd, we must have $\alpha_i=1$ for every $i \leq k$, and also $p_i-1=2^{\beta_i}$ for suitable $\beta_i=2^{\gamma_i}$'s: all the $p_i$'s are Fermat primes. But then $\prod _{i=1} ^k p_i ^{\alpha _i-1}(p_i-1)=\prod _{i=1} ^k (p_i-1)=\prod _{i=1} ^k 2^{2^{\gamma_i}}$. Now, we have $2^{2^{\gamma_i}} \equiv -1 \pmod {p_i}$ from which $\text{ord}_{p_i}(2)=2^{\gamma_i+1}$, but since also $2^{x+1} \equiv 1 \pmod {p_i}$ we get that $2^{\gamma_i+1}$ divides $x+1$. In particular, this holds for $\max _i \gamma_i$; since $x=\sum _{i=1}^k 2^{\gamma_i}$, it follows that $x+1=2^{\max _i \gamma_i+1}$, so it also follows that the $\gamma_i$'s are consecutive numbers. But it is easily checked that ${2^{2^5}}+1$ is not prime (in fact, it is a multiple of $641$), while the preceeding Fermat numbers are primes. We deduce that the solutions are $x=0, 1, 3, 7, 15$, which indeed work.
30.05.2021 19:15
dinoboy wrote: It can easily be determined only Fermat primes satisfy this equation... however it is an open problem as to if there are infinitely any Fermat primes beyond $2^{2^4} + 1$, so this problem can't really be solved. No, this isn't accurate. The moment some Fermat number is not a prime, no higher Fermat numbers work.