MHB Congruences - Rotman - Proposition 1.58

  • Thread starter Thread starter Math Amateur
  • Start date Start date
Math Amateur
Gold Member
MHB
Messages
3,920
Reaction score
48
I am reading Joseph J.Rotman's book, A First Course in Abstract Algebra.

I am currently focused on Section 1.5 Congruences.

I need help with the proof of Proposition 1.58 part (ii) ...

Proposition 1.58 reads as follows:https://www.physicsforums.com/attachments/4521
View attachment 4522In the above text ... specifically, in the proof of Part (ii) we read:

" ... ... (ii) If $$r = r' \text{ mod } m$$, then $$m \mid (r - r')$$ and $$m \le r - r'$$ . ... ... "


Can someone show me precisely and formally how $$r = r' \text{ mod } m$$ implies that $$m \le r - r'$$ ...

It seems quite plausible ... but how do we formally and rigorously show this ...

Peter
 
Physics news on Phys.org
If $m>0$ and $n\ge0$ are integers, then $m\mid n$ means that $n=km$ for some nonnegative integer $k$. If $k=0$, then $n=0$; if $k\ge1$, then $n\ge m$. Therefore, if $r\equiv r'\pmod{m}$, then $m\mid (r-r')$ and therefore either $r-r'=0$ or $r-r'\ge m$. The first option is impossible because by assumption $r'<r$, and the second option is impossible because $r<m$.
 
Evgeny.Makarov said:
If $m>0$ and $n\ge0$ are integers, then $m\mid n$ means that $n=km$ for some nonnegative integer $k$. If $k=0$, then $n=0$; if $k\ge1$, then $n\ge m$. Therefore, if $r\equiv r'\pmod{m}$, then $m\mid (r-r')$ and therefore either $r-r'=0$ or $r-r'\ge m$. The first option is impossible because by assumption $r'<r$, and the second option is impossible because $r<m$.

Thanks Evgeny ... I very much appreciate your help ...

Peter
 
Back
Top