Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $n \in \mathbb{N}$ with $(n,\varphi(n))=1$ , where $\varphi$ is the Euler-totient function. Prove the equation $x^x \equiv c \pmod{n}$ has integer solution for all $c \in \mathbb{N}$

My thought: By Euler's theorem one has $\varphi(n)^{\varphi(n)} \equiv 1 \pmod{n}$, so I need to find an $x$ such that $x^x \equiv c \varphi(n)^{\varphi(n)} \equiv c \pmod{n}$. It seems one needs to consider the primitive roots $\bmod(n)$ somehow, but $c$ may not be coprime to $n$.

share|improve this question
    
Primitive root won't work, most $n$ don't have one. –  André Nicolas Jul 24 '12 at 0:15
    
If $\gcd(c,n)=1$, then choose $k$ such that $c+kn\equiv1\pmod{\phi(n)}$, and you get $(c+kn)^{c+kn}\equiv c\pmod n$. Still working on $\gcd(c,n)\gt1$.... –  Gerry Myerson Jul 24 '12 at 1:14
    
One thing's sure: $\,n\,$ must be odd... –  DonAntonio Jul 24 '12 at 2:00
    
@Don, $n=2$ seems to be OK. Other even values of $n$ are ruled out by the hypothesis, $\gcd(n,\phi(n))=1$. –  Gerry Myerson Jul 24 '12 at 2:32
    
I think the question can be generalized with Carmichael Function in place of Euler-totient function. mathworld.wolfram.com/CarmichaelFunction.html –  lab bhattacharjee Jul 26 '12 at 5:36
add comment

1 Answer

up vote 1 down vote accepted

First, note that the hypothesis $\gcd(n,\phi(n))=1$ implies that $n$ is a product of distinct primes (since $p^2\mid n$ implies $p\mid\phi(n)$).

Now we deduce that $${\rm if\ }\gcd(n,\phi(n))=1{\rm\ then\ }a^{1+k\phi(n)}\equiv a\pmod n{\rm\ for\ all\ }k.$$ Let $p$ be a prime dividing $n$. If $a\equiv0\pmod p$, then surely $a^{1+k\phi(n)}\equiv a\pmod p$, since both sides of the congruence are zero. If $\gcd(a,p)=1$, then $$a^{1+k\phi(n)}=a^{1+k'(p-1)}=a\bigl(a^{p-1}\bigr)^{k'}\equiv a\pmod p$$ for some integer $k'$. Thus we have $a^{1+k\phi(n)}\equiv a\pmod p$ for all primes $p$ dividing $n$. Since these primes are pairwise coprime, and since $n$ is their product, $a^{1+k\phi(n)}\equiv a\pmod n$ follows by the Chinese Remainder Theorem.

Now, given $c$, choose $k$ such that $1+k\phi(n)\equiv c\pmod n$. Again, the hypothesis $\gcd(n,\phi(n))=1$ guarantees $k$ exists. Now $$(1+k\phi(n))^{1+k\phi(n)}\equiv c^{1+k\phi(n)}\equiv c\pmod n$$ and we are done; we have shown we can take $x=1+k\phi(n)$.

share|improve this answer
    
Nice solution! The core relation $a^{1+k\phi(n)}\equiv a\pmod n$ is so powerful which helps to avoid discussion in several cases..Thanks! –  user31899 Jul 24 '12 at 4:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.