2
$\begingroup$

The question says:

Prove that if $a$ is of order $3$ modulo a prime $p$, then $1+a+a^2\equiv 0 \pmod p$. Moreover, $a+1$ is of order $6$.

For the First Part:

The typical idea is to start with $a^3 \equiv 1 \pmod p \to a^3 -1 \equiv 0 \pmod p$. Factoring the term on the left hand side, the rest is straightforward.

However, I need to check the following idea:

$$1+a+a^2 \equiv a^3+a^2+a \equiv a(1+a+a^2)\equiv a^2(1+a+a^2)$$ $$\equiv a^3(1+a+a^2) \equiv 0 \pmod p$$

Since, by the hypothesis, $a^3$ cannot be zero modulo the prime $p$, the desired result holds.

If this idea holds true, it can be generalized to the following result:

if $a$ is of order $k$, then, modulo prime $p$, then $1+a+a^2+\cdots + a^{k-1}$ is divisible by $p$.

Is it??

For the Second Part:

I can see that:

$$1+a+a^2 \equiv 0 \to 1+a \equiv -a^2 \pmod p$$

However, does this implies anything? Given that $a$ is of order $3$, but what about $-a$??

Please Help, and Thanks in advance,,

$\endgroup$
2
$\begingroup$

For the second part, taking from the first part that $1+a = -a^2\pmod p\implies (1+a)^6= (-a^2)^6 = a^{12}\pmod p= (a^3)^4 =1^4\pmod p=1\pmod p$ . Thus $1+a$ is of order $6$ as claimed. And if $a$ is of order $3$ then $(-a)^3 = -a^3 = -1 = p-1\pmod p$. And from this we have: $(-a)^6 = ((-a)^3)^2 = (-1)^2 = 1\pmod p$. So $-a$ is of order $6$ as well.

$\endgroup$
  • $\begingroup$ Thanks, but how to be sure that $6$ is the least power congruent to $1 \pmod p$ for $(1+a)$?? $\endgroup$ – Maged Saeed Nov 23 '18 at 4:28
  • $\begingroup$ I need also to make sure my thoughts are correct for the first part. Thanks in advance. $\endgroup$ – Maged Saeed Nov 23 '18 at 4:29
  • 1
    $\begingroup$ @MagedSaeed: You can prove it yourself that if $k$ is such that $(a+1)^k = 1\pmod p \implies k = 6$. In fact, such $k$ must satisfies $k \mid 6 \implies k = 1,2,3$. And none of these can satisfy since $a$ is of order $3$. $\endgroup$ – DeepSea Nov 23 '18 at 4:35
  • $\begingroup$ Oh, thanks,, I see. $\endgroup$ – Maged Saeed Nov 23 '18 at 4:37
0
$\begingroup$

Using geometrical sum formula we get

$$1+a+a^2 = \frac{a^3-1}{a-1} \equiv 0 \pmod p$$

And generally we get

$$1+a+a^2+\dots + a^{k-1}= \frac{a^k-1}{a-1} \equiv 0 \pmod p$$

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