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.

enter image description here

enter image description here

enter image description here

I am trying to understand fermat's little theorem in residue classes but the below slides make absolutely no sense to me. In computer classes a' means if you have 3 then 3' would be 6 because 3+6=9 so I am really confused here about what they are doing..

I know that residue classes mod m basically means the remainder when mod by m but I dont really understand what they mean or do by [a][b]=[a'][b']

Also, really not sure how they are finding the inverse...the general equation is a congruent to b (mod m)

share|improve this question

1 Answer 1

up vote 3 down vote accepted

The primes in the statement of prop 4.2.2 are not operators; $a'$ and $b'$ are simply names of variables which are different from $a$ and $b$, although suggestively named.

It is, however, not very clearly written. It appears that the author is using $[a]$ and $[a']$ denote the residue classes of the integers $a$ and $a'$, and so forth. But it is strictly speaking nonsense to write "if $[a]=[a']$ and $[b]=[b']$ modulo $m$ ...". For then $[a]=[a']$ simply asserts that the residue classes are the same, and this identity is just an identity between sets of numbers; there is nothing modular about the way these sets are equal.

But if the author does mean the premises to be $[a]=[a']$ and $[b]=[b']$, then the conclusions $[a]+[b]=[a']+[b']$ and $[a][b]=[a'][b']$ are completely vacuous, because of course we're allowed to substitute equals for equals.

What the proposition ought to have been, in order to be meaningful, is

If $a\equiv a'\pmod m$ and $b\equiv b'\pmod m$, then $(a+b)\equiv(a'+b')\pmod m$ and $ab\equiv a'b' \pmod m$.

or, equivalently,

If $[a]=[a']$ and $[b]=[b']$, then $[a+b]=[a'+b']$ and $[ab]=[a'b']$.

... and because of this fact it is possible and meaningful to define the sum and product of residue classes by $[a]+[b]=[a+b]$ and $[a]\cdot[b]=[ab]$.

share|improve this answer

Your Answer


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.