4
$\begingroup$

This question already has an answer here:

Fermat's little theorem states that if $p$ is a prime number, then for any integer $a$, the number $a^{p} − a $ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed as $a^{p} \equiv a \pmod p.$

Using this theorem prove:

Given a prime number $p$, show that if there are a positive integer $x$ and a prime number $a$ such that $p$ divides $\frac{x^{a}-1}{x-1}$, then either $a = p$ or $p \equiv 1 \pmod a$.

$$p\mid\frac{x^{a}-1}{x-1}$$

So, I'm thinking: $$\frac{x^{a}-1}{x-1} = x^{a-1}+x^{a-2}+...+1$$ I tried the telescoping technique but that doesn't work, assuming $a = p$, shows that $x^{p-1}\equiv 1 \pmod p$.

So, what else can I do?

$\endgroup$

marked as duplicate by Andreas Caranti, Namaste, John B, Callus, Michael Hoppe Jan 4 '17 at 18:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Sure about "a=p" ? $\endgroup$ – Peter Jan 2 '17 at 20:55
  • 1
    $\begingroup$ I don't know, I found this exercise online. There are some which are relatively poorly written.. :/ $\endgroup$ – Fate Metric Jan 2 '17 at 20:59
2
$\begingroup$

You have:

$p|\frac{x^a-1}{x-1}\Rightarrow p|(\frac{x^a-1}{x-1})(x-1) \Rightarrow p|x^a-1 \Rightarrow x^a \equiv 1 (\mod p)$

Hence if $m$ is the order of $x$ with respect to $p$, then $m|a \Rightarrow m=1$ or $m=a$, since $a$ is prime.

If $m=1$, then by the definition of the order, we have that $x\equiv 1(\mod p)$ and so by the hypothesis we get:

$0\equiv \frac{x^a-1}{x-1}\equiv x^{(a-1)}+...+1\equiv 1^{(a-1)}+...+1\equiv a(\mod p)$

Hence in this case $p|a \Rightarrow p=1\ \text{or}\ p=a$, since $a$ is a prime. The first equality is rejected, because $p>1$ as a prime number.

If $m=a$, then $a|p-1 \Rightarrow p\equiv 1 (\mod a)$, because it is known that for the order $m$ we have $m|φ(p)$. $φ$ is the Euler totient function.

The proof of the property that $m$ holds uses the Fermat's little Theorem.

Links:

1.Orders

2.Euler's Totient Function

$\endgroup$
  • $\begingroup$ I don't understand how you got that $x^{a}\equiv 1 (\mod {p})$ from $p|x^{a}-1$. $\endgroup$ – Fate Metric Jan 3 '17 at 9:41
  • $\begingroup$ @FateMetric The definition of modulo n equivalence is: $a\equiv b (\mod n)$ iff $n|a-b$ $\endgroup$ – Stelios Sachpazis Jan 3 '17 at 9:57
  • $\begingroup$ Can we have a live conversation? I want to ask you more about this. $\endgroup$ – Fate Metric Jan 4 '17 at 10:41
  • $\begingroup$ @FateMetric Yes, but tell me where and how, because I am new here. $\endgroup$ – Stelios Sachpazis Jan 4 '17 at 10:44
  • $\begingroup$ @FateMetric I would prefer chatting in a forum. $\endgroup$ – Stelios Sachpazis Jan 4 '17 at 13:32
1
$\begingroup$

If $p$ divides $\frac{x^a-1}{x-1}$, it must also divide $x^a-1$, so we can conclude $$x^a\equiv 1\mod p$$

Let $o$ be the smallest non-zero number $o$ with $x^o\equiv 1\mod p$, also called the order of $x$ modulo $p$

Then $a$ must be a mutiple of $o$, but $a$ is prime. So, either we have $o=1$, in which case we have $p|x-1$ , in other words $x\equiv 1\mod p$ or we must have $a=o$, in which case we can conclude $a|p-1$ , in other words $p\equiv 1\mod a$

$\endgroup$
1
$\begingroup$

Since $p\mid \frac{x^a-1}{x-1}$ can be expressed as $\frac{x^a-1}{x-1} = pk + 0$ thus operating we have $x^a = (x-1)kp + 1$ and in modular form $x^a \equiv 1 \pmod p$.

Then through the last one we know that $Ord_p(x)=a$ and that $a|\varphi(p)$ that is $p-1 \equiv 0 \pmod a$ so $p \equiv 1 \pmod a$ holds.

$\endgroup$

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