# divisibility remains by scaling multiplicative order [duplicate]

I want to show that if p | $$a^{e}-1$$ then also p | $$a^{ek}-1$$ where k is any integer.

Def. of order in terms of divisibility: Let $$m ≥ 2$$ and a be any integer coprime to $$m$$. The order of $$a$$ mod $$m$$ is the smallest $$e > 0$$ so that $$m$$ divides $$a^{e}-1$$.

In terms of congruence I can see why this is the case: e.g. let $$a = 2, e = 4, m = 5$$. Then

$$2^{4} ≡ 1$$ (mod $$5$$), lets scale $$e$$ with $$k=2$$, then $$2^{4^2} ≡ 1$$ (mod $$5$$) = $$2^{4}2^{4} ≡ 1$$ (mod $$5$$). So it does not matter what $$k$$ is, the congruence is still valid.

I don't know exactly how to show why the scaling of $$e$$ with any $$k$$ does not change the fact that $$p$$ divides $$a^{e}-1$$.

• $\,p\mid a^e-1\mid a^{ek}-1\,$ by the first linked dupe with $\, a \to a^e,\ b = 1,\ n = k.\$ Or use $\bmod p\!:\ a^e\equiv 1\Rightarrow (a^e)^k\equiv 1^k\equiv 1\,$ by the Congruence Power Rule, or if $\ell := {\rm ord}_p \,a\,$ then $\,\ell \mid e\Rightarrow \ell\mid ek\Rightarrow a^{ek}\equiv 1\,$ by the Order Theorem. Commented Jun 23, 2021 at 19:11

If $$p|a^e-1$$, then $$pc=a^e-1$$ for some $$c$$, and so $$pc+1=a^e$$.
Then $$(pc+1)^k=a^{ek}$$, and the left hand side is $$pb+1$$ for some $$b$$, hence $$pb=a^{ek}-1$$, or $$p|a^{ek}-1$$.
Observe, $$a^{ek}-1=(a^e)^k-1^k=(a^e-1)\cdot q$$ for some integer $$q$$.
Since $$p$$ divides $$a^e-1$$, it must divide $$a^{ek}-1$$.
• Factorize $a^n-b^n$ Commented Jun 23, 2021 at 11:45
• I think I understood your explanation, but the .q is a bit unclear for me. Let me try to summarize your point in my own words: $a^{ek}-1=(a^e)^k-1^k$. This is clear. The next step is $p | (a^e-1)^k$. And since $p | a^e - 1$, $p$ also divides $(a^e - 1)^k$ Commented Jun 23, 2021 at 12:09
• We know for a fact that $p\;|\;a^e-1$. In the first step, we show that $a^e-1\;|\;a^{ek}-1$. Therefore $p\;|\;a^e-1\;|\;a^{ek}-1.$ The term ' $q$ ' is the quotient when $a^{ek}-1$ is divided by $a^e-1$. Hope it helps :) Commented Jun 23, 2021 at 12:15
• Think about it this way. In the equation, $$a^{ek}-1=(a^e-1)\cdot q$$ $p$ appears in the prime factorization of $a^e-1$ on the right hand side. Hence, it also appears on the left side. Therefore, $p$ divides $a^{ek}-1$. Commented Jun 23, 2021 at 12:19