1
$\begingroup$

Prove or disprove that

$$ a^{\phi(n) + k} \equiv a^{k} \mod{n} $$ where $\phi(n)$ is Euler's totient function, for all positive integers $a$ and $n$, as long as $k$ is $\geq$ the multiplicity of all the primes in the factorization of $n$.

I saw the above corollary in Brilliant, so how do you prove (or disaprove) it? Because for $a^{\phi(n) + 1} \equiv a \mod{n}$, it seems to work

$\endgroup$
3
  • $\begingroup$ You missed the condition that $k\ge$ the largest mulitplicity of the primes in the prime decomposition of $n$ that was in the Brilliant post. That makes the theorem true. $\endgroup$ – user26486 May 22 '15 at 22:33
  • $\begingroup$ @user31415 You right, thank you and sorry. $\endgroup$ – antoniov.joel May 22 '15 at 22:38
  • 1
    $\begingroup$ Why is the proof provided by Otto Bretscher not satisfying enough? Any answer proving this theorem would basically be a duplicate of his proof. $\endgroup$ – user26486 May 22 '15 at 23:01
1
$\begingroup$

Without restriction on $n$ or $a$, it's not always true for small values of $k$ (but always true for "big enough" $k$).

For a counterexample, $\phi(9) = 6$ and $3^7 \not \equiv 3^1 \bmod 9$.

For $a,n$ not coprime, $k$ needs to be big enough to "saturate" the biggest shared prime factor. For any $a$ given $n$, $k\ge\alpha_{max}$ is certainly big enough, where $\alpha_{max}$ is the biggest prime exponent in the prime decomposition of $n$.

$\endgroup$
2
  • $\begingroup$ That's the additional condition that was in the Brilliant post mentioned in OP. I.e. $k\ge$ the largest multiplicity of the primes in the prime decomposition of $n$. $\endgroup$ – user26486 May 22 '15 at 22:30
  • $\begingroup$ @user31415 Yes, I went to look at the article afterwards. Some interesting work there. I see the OP has revised now to include that condition, which thus needs a proof rather than a disproof. $\endgroup$ – Joffan May 22 '15 at 22:41
0
$\begingroup$

Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$. Two cases: $\,p_i\mid a\,\stackrel{k\ge\alpha_i}\Rightarrow\, p_i^{\alpha_i}\mid a^k\,\Rightarrow\, a^{\varphi(n)+k}\equiv a^k\equiv 0\pmod{p_i^{\alpha_i}}$

$p_i\nmid a\,\stackrel{\text{ET}}\Rightarrow\, a^{\varphi(p_i^{\alpha_i})}\equiv 1\pmod{\! p_i^{\alpha_i}}$. Raise by $\frac{\varphi(n)}{\varphi(p_i^{\alpha_i})}\in\Bbb N$: $a^{\varphi(n)}\equiv 1\pmod{\!p_i^{\alpha_i}}$. Multiply by $a^k$.

Remarks: ET - Euler's theorem. $\varphi(p_i^{\alpha_i})\mid \varphi(n)$ is because

$p_i^{\alpha_i}-p_i^{\alpha_i-1}\mid \left(p_1^{\alpha_1}-p_1^{\alpha_1-1}\right)\cdots\left(p_k^{\alpha_k}-p_k^{\alpha_k-1}\right)$

We can raise, i.e. $a\equiv b\,\Rightarrow\, a^m\equiv b^m$, because $a^m-b^m=(a-b)(a^{m-1}+\cdots+b^{m-1})$

This is what Bill Dubuque calls Congruence Power Rule (see for another proof).

$a^{\varphi(n)+k}\equiv a^k\pmod{\! p_i^{\alpha_i}}$ for arbitrary $i\in\{1,\ldots,k\}$ iff $a^{\varphi(n)+k}\equiv a^k\pmod{\! n}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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