Let $n$ be an odd positive integer such that $\varphi (n)$ and $\varphi (n+1)$ are both powers of $2$ (here $\varphi(n)$ denotes Euler’s totient function). Prove that $n+1$ is a power of $2$ or $n = 5$.
Problem
Source: India Postal Set 1 P1 2016
Tags: number theory
18.01.2017 07:31
What about $n=16,\ n+1=17$?
18.01.2017 07:34
@above $n$ is an odd positive integer.
18.01.2017 10:15
Recycled. See here http://www.artofproblemsolving.com/community/c6h401067p2233187
18.01.2017 10:50
Suppose to the contrary that $n+1$ is not a power of $2$ and $n\neq 5$ Let $n=\prod_{i=1}^{k}{p_i^{a_i}}$ and $n+1=\prod_{i=1}^{l}{q_i^{b_i}}$ where $p_1<p_2<...<p_k,q_1<q_2<...<q_l$ are prime numbers. We get that $\varphi (n)=\prod_{i=1}^{k}{p_i^{a_i-1}}\prod_{i=1}^{k}{(p_i-1)}$ and $\varphi (n+1)=\prod_{i=1}^{l}{q_i^{b_i-1}}\prod_{i=1}^{l}{(q_i-1)}$ are both power of $2$ So $a_1=a_2=...=a_k=1$ and $b_2=b_3=...=b_l=1$ and $p_1,p_2,...,p_k,q_2,q_3,...,q_l$ must be prime number of the form $2^t+1$ for some $t\in \mathbb{Z}^+$ Note that $p_1,p_2,...,p_k,q_2,q_3,...,q_l$ are pairwise distinct (since $gcd(n,n+1)=1$) and all of them must be Fermat number. We also get that $\Big( \prod_{i=1}^{k}{p_i}\Big) +1=n+1=2^{b_1}\prod_{i=2}^{l}{q_i}$ Suppose $q_l>p_k$, suppose $q_l=2^{2^w}+1$, we get that $LHS> q_l=2^{2^w}+1=\Big( \prod_{i=1}^{w-1}{(2^{2^i}+1)}\Big) +2>\Big( \prod_{i=1}^{k}{p_i}\Big) +1$, contradiction So $p_k>q_l$, suppose $p_k=2^{2^v}+1$ If $k=1$ we get $p_1+1=2^{b_1}\prod_{i=2}^{l}{q_i}=\Big( \prod_{i=1}^{v-1}{(2^{2^i}+1)}\Big) +3$, so $\prod_{i=2}^{l}{q_i}\mid 3\Rightarrow l=2,q_2=3$, thus $p_1=3\times 2^{b_1}-1\Rightarrow 2^{2^v}=3\times 2^{b_1}-2$ So $b_1=1$, otherwise we get $2^v=2$ and so $n=5$, contradiction, but $b_1=1$ give us $2^{2^v}=0$, impossible. Now we left the case $k\geq 2$, we will consider in two cases. If $2^{b_1}<p_k$, we get $p_k\equiv_{2^{b_1}} 1$, so $\Big( \prod_{i=1}^{k-1}{p_i} \Big) +1\equiv_{2^{b_1}} 0$ If $2^{b_1}\geq p_k$, we get that $\prod_{i=1}^{k}{p_i}\equiv_{2^{b_1}} -1$ Let $2^{2^z}\leq 2^{b_1}\leq 2^{2^{z+1}-1}$ Both case give us there exist Fermat numbers $w_1,w_2,...,w_h$ all less than $2^{b_1}$ such that $w_1w_2...w_h+1\equiv_{2^{2^z}} F_1F_2...F_{z-1}+1$ So $\frac{F_1F_2...F_{z-1}}{w_1w_2...w_h} \equiv_{2^{2^z}=F_1F_2...F_{z-1}-1} 1$, this give us $\{ w_1,w_2,...,w_h\} =\{ F_1,F_2,...,F_{z-1}\}$ In the case $2^{b_1}\geq p_k$, we get that $h=k$ and so $1+\prod_{i=1}^{k}{p_i} =2^{2^z}<2^{b_1}\prod_{i=2}^{l}{q_i}$, contradiction. And in the case $2^{2^z}<2^{b_1}<p_k$, we get that $p_1=F_1,p_2=F_2,...,p_{k-1}=F_{z-1}$ So we have $p_k(2^{2^z}-1)+1=2^{b_1}\prod_{i=2}^{l}{q_i}$ So $q_2,q_3,...,q_l\geq 2^{2^z}+1$, so $p_k(2^{2^z}-1)<LHS=RHS< (2^{2^{z+1}-1}) \frac{p_k}{F_1F_2...F_{z-1}=2^{2^z}-1}$ We get that $(2^{2^z}-1)^2\leq 2^{2^{z+1}-1}$ which is false for all $z\in \mathbb{Z}^+$, done. .
19.12.2021 13:11
Anyone can say about this contest