2
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ $\,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. $\endgroup$ Commented Jun 23, 2021 at 19:11

2 Answers 2

4
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
4
  • 1
    $\begingroup$ Factorize $a^n-b^n$ $\endgroup$
    – Sathvik
    Commented Jun 23, 2021 at 11:45
  • $\begingroup$ 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$ $\endgroup$
    – Banause
    Commented Jun 23, 2021 at 12:09
  • 1
    $\begingroup$ 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 :) $\endgroup$
    – Sathvik
    Commented Jun 23, 2021 at 12:15
  • $\begingroup$ 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$. $\endgroup$
    – Sathvik
    Commented Jun 23, 2021 at 12:19

Not the answer you're looking for? Browse other questions tagged .