- If $a$, $b$ are coprime, then $$a^{\phi(b)}+b^{\phi(a)}\equiv 1 \bmod (ab) \, .$$
- If $\left(n=2\phi(n)\right)$, then $n$ is a power of $2$.
Problems with Euler $\phi$ function (2)
3
$\begingroup$
number-theory
elementary-number-theory
prime-numbers
totient-function
-
0(1) is a generalization of http://math.stackexchange.com/questions/248219/two-problem-number-theory. – 2012-12-01
2 Answers
2
1) It is easy to use Euler's theorem to verify that $a^{\phi(b)}+b^{\phi(a)}=1$ (mod a), similarly $a^{\phi(b)}+b^{\phi(a)}=1$ (mod b). Since a,b are coprime we get: $a^{\phi(b)}+b^{\phi(a)}=1$ (mod ab)
2)Let $n=i2^j$ (where i is odd). $\phi(n)=\phi(2^j)\phi(i)=2^{j-1}\phi(i)=n/2$, thus $n=2^j\phi(i)$. Therefore $\phi(i)=i$, hence $i=1$
-
0why $\phi(i)$=i?andi=1? – 2012-12-01
-
0if $\phi(i)=i$, it follows that all numbers in the set {1,2,...,i} are coprime to $i$, thus $i,i$ are coprime. Hence, $i=1$ – 2012-12-01
-
0Yes, which is $2^{a-1}$ – 2012-12-01
-
0@Amr: Oh sorry! – 2012-12-01
-
0if n isn't equal $i2^j$ then ...? can you solve this problem generality? – 2012-12-01
-
0This is the contrapositive of what I proved. – 2012-12-01
2
Hint: For (2): Since $$\varphi(n)=n\prod_{p|n}\left(1-\frac1p\right)$$ Saying that $n=2\varphi(n)$ is equivalent to $\prod_{p|n}\left(1-\frac1p\right)=\frac12$. Can you show that this implies that if $p|n$ then $p=2$?
-
0I cann't show that n is power of 2,please help me. – 2012-12-01
-
0Assume that there exists $p|n$, $p\neq 2$. Then $\frac{p-1}{p}$ appears in the product. Since $p+1$ is not a prime, $p$ does not appear in the numerator in any factor. Hence $p$ remains in the denumerator in the result as well. – 2012-12-01