Congruences

Recall that for integers and a fixed integer , we define if and only if . In this case, we say that is congruent to modulo .

• Application: Divisibility criteria revisited
• Aside on equivalence relations
• Properties of
• Repeated squaring algorithm
• Fermat's little theorem
• Linear recurrence equations
• Application: Two ciphers
  • Caesar's cipher
  • A stream cipher: linear feedback shift registers
  
  
• Feedback with carry shift register ciphers
• Application: calendar calculations
  • First method
  • Second method (due to Conway)
  
  
• The Chinese remainder theorem
  • General Chinese remainder theorem
  
  
• An application to Euler's -function