Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
Two numbers $a$ and $b$ are relatively prime if $\textrm{GCD}(a,b) = 1$. –  dtldarek Dec 3 '12 at 10:16
    
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$. –  Shubhodip Mondal Dec 3 '12 at 10:17
    
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$. –  Adam Bailey Dec 3 '12 at 12:22

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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