3
$\begingroup$

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

Use Fermat's little theorem to prove that:

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

I tried to connect $\frac{x^a – 1}{x – 1}$ to the theorem, but without any success.. Anything will help.. Thanks in advance Picture in addition same as the text

$\endgroup$
1
$\begingroup$

The statement is not correct. If $x \equiv 1 \mod p,$ and $a\equiv 0 \mod p,$ then $p$ divides your expression.If $x$ is not $1$ modulo $p,$ the denominator is not divisible by $p,$ so the expression is divisible by $p$ if and only if the numerator is, or, if and only if $x^a \equiv 1 \mod p.$ This last has a solution whenever $a$ divides $p-1,$ or, more generally, $a$ is not relatively prime to $p-1.$

$\endgroup$
  • $\begingroup$ Was the Q altered after your answer? Because my A is a proof. Note that the $a$ in the Q is prime. Was that always there? $\endgroup$ – DanielWainfleet Jan 2 '17 at 10:48
  • $\begingroup$ @user254665 No, it was not. Interesting. $\endgroup$ – Igor Rivin Jan 2 '17 at 11:59
1
$\begingroup$

(1). If $1\ne x\equiv 1 \pmod p,$ let $x=1+py.$ Then by the Binomial Theorem, $$x^a-1=(1+py)^a-1=\left(1+\binom {a}{1}py+...\right)-1=apy +(py)^2z$$ where $z$ is an integer . So $$\frac {1}{p} \frac {x^a-1}{x-1}=\frac {1}{p} \frac {apy +(py)^2z}{py}=\frac {a}{p}+yz.$$ This is an integer iff $p|a.$ If $a$ and $p$ are prime, $p|a\implies p=a.$

(2A). For prime $p$ and $p\not | x,$ let $ord_p(x)$ be the least $n>0$ such that $x^n\equiv 1 \pmod p.$ Then for $m>0$ we have $$x^m\equiv 1 \pmod p\implies ord_p (x)|m.$$ Proof: There are positive integers $A, B$ with $$A\cdot ord_p(x)-Bm=\gcd (ord_p(x),m).$$ Therefore $$1\equiv x^{A\cdot ord_p(x)}\equiv x^{Bm}x^{\gcd (ord_p(x),m)}\equiv x^{\gcd (ord_p(x),m)} \pmod p.$$ So by the def'n of $ord_p(x)$ we must have $\gcd (ord_p(x),m)\geq ord_p (x).$ But $\gcd (ord_p (x),m)$ cannot be greater than $ ord_p (x).$ So $ord_p (x)=\gcd (ord_p (x),m),$ which is equivalent to $ord_p(x)|m.$

(2B). From (2A) and Fermat's Little Theorem , we have: If $p,a$ are primes and $x\not \equiv 1 \pmod p$ then $$x^a\equiv 1\pmod p\implies (a=ord_p(x)\land a|(p-1).)$$ Because $ord_p(x)>1,$ and (2A) implies $ord_p(x)|a,$ so $ord_p(x)=a.$ Then by Fermat we have $a=ord_p(x)|(p-1).$

(3). We use (2B) to handle your Q for the case $x\not \equiv 1 \mod p.$

(i). If $p|x$ then $p\not | \;(x^a-1)$ so this case is moot.

(ii). If $0\not \equiv x\not \equiv 1 \pmod p$ then $$p|(x^a-1)/(x-1)\implies p|(x^a-1)$$ with prime $a,$ so by (2B), $a|(p-1).$ That is, $p\equiv 1 \pmod a. $

Remark: The results of (2A) and (2B) are commonly used tools.

$\endgroup$
  • $\begingroup$ Could you explain how $$x^a-1=(1+py)^a-1=\left(1+\binom {a}{1}py+...\right)-1$$ is equal to $$apy +(py)^2z$$ where $z$ is an integer $\endgroup$ – Math Newbie Jan 2 '17 at 11:49
  • $\begingroup$ $(1+py)^a-1=apy+\sum_{j=2}^a\binom {a}{j}(py)^j.$ Now each $\binom {a}{j}$ is an integer. And $(py)^j$ is divisible by $(py)^2$ when $j\geq 2.$ So each term $\binom {a}{j}(py)^j,$ for $j\geq 2$ , is divisible by $(py)^2 .$ $\endgroup$ – DanielWainfleet Jan 3 '17 at 2:36
1
$\begingroup$

We have that $p \mid x^a - 1$, or $x^a \equiv 1 \pmod{p}$. So first of all $x \not\equiv 0 \pmod{p}$, so that $x^ p - x \equiv 0 \pmod{p}$ implies $x^{p-1} \equiv 1 \pmod{p}$. (As the prime $p$ divides $x^ p - x = x (x^{p-1} - 1)$, and $p \nmid x$.)

And then, $a$ being prime, $x$ has order either $1$ or $a$ modulo $p$. Of course order $1$ means $x \equiv 1 \pmod{p}$. But then $$ \frac{x^a - 1}{x - 1} = x^{a-1} + \dots + x + 1 \equiv a \equiv 0 \pmod{p}, $$ so that $p \mid a$ and thus $p = a$.

If $x$ has order $a$ modulo $p$, then $a$ must divide the order $p-1$ of the group of invertible integers modulo $p$. I guess this is where Fermat' s Little Theorem might come in. First of all, $$ x^a \equiv 1 \pmod{p}, \quad x^{p-1} \equiv 1 \pmod{p} $$ imply that if $p-1 = a q + r, 0 \le r < a$ (so that $r$ is the remainder of the division of $p-1$ by $a$) then $$ x^{p-1} \equiv x^{a q + r} \equiv x^r \equiv 1 \pmod{p}, $$ so that $r = 0$, as $r$ is less than the order $a$ of $x$ modulo $p$.

$\endgroup$
  • $\begingroup$ How did you come to this : And then, $a$ being prime, $x$ has order either $1$ or $a$ modulo $p$. Of course order $1$ means $x \equiv 1 \pmod{p}$. Is there a rule for that part ? $\endgroup$ – Math Newbie Jan 2 '17 at 13:45
  • $\begingroup$ I am using the fact that if an element $x$ of a finite group has order $m$, then $x^a = 1$ iff $m \mid a$. $\endgroup$ – Andreas Caranti Jan 2 '17 at 13:46

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.