4
$\begingroup$

I'm reading mathematical gems, Vol.1:

He states the Fermat's little theorem:

If $p$ is a prime number, then for every integer a, the number $a^p-a$ is divisible by $p$.

And then there's an addendum:

Actually he stated the equivalent theorem: If $p$ is prime, then $p$ divides $a^{p-1}-1$ for every integer $a$ that is relatively prime to $p$.

I didn't get the meaning of the bold part.

What's the meaning of this?

  • 3
    Two numbers $a$ and $b$ are relatively prime if $\textrm{GCD}(a,b) = 1$.2012-12-03
  • 0
    Actually $a$ is relatively prime to $p$ means $a$ is not divisible by $p$. Since $p \mid a^p -a = a(a^{p-1} - 1)$ , if $p$ doesn't divide $a$, we must have that $p$ divides $a^{p-1} - 1$.2012-12-03
  • 0
    The significance of the condition on $a$ is seen by noting that if $a$ is divisible by $p$ then so is $a^{p-1}$ and therefore $a^{p-1}-1$ cannot be divisible by $p$.2012-12-03

2 Answers 2

6

Two positive integers $x$ and $y$ are relatively prime or coprime if they have no common factor other than $1$. In the case one of them is prime, say $x$, this is equivalent to saying that $x$ does not divide $y$.

1

2 Numbers are relatively prime (or coprime ) if they dont have any common factor other than 1 .

Eg 14 and 15 are relatively prime ,

whereas 14 and 21 are not relatively prime , because of the common factor 7.