Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

3: Congruences

( \newcommand{\kernel}{\mathrm{null}\,}\)

A congruence is nothing more than a statement about divisibility. The theory of congruences was introduced by Carl Friedreich Gauss. Gauss contributed to the basic ideas of congruences and proved several theorems related to this theory. We start by introducing congruences and their properties. We proceed to prove theorems about the residue system in connection with the Euler ϕ-function. We then present solutions to linear congruences which will serve as an introduction to the Chinese remainder theorem. We present finally important congruence theorems derived by Wilson, Fermat and Euler.

  • 3.1: Introduction to Congruences
    As we mentioned in the introduction, the theory of congruences was developed by Gauss at the beginning of the nineteenth century.
  • 3.2: Residue Systems and Euler’s φ-Function
  • 3.3: Linear Congruences
    Because congruences are analogous to equations, it is natural to ask about solutions of linear equations. In this section, we will be discussing linear congruences of one variable and their solutions.
  • 3.4: The Chinese Remainder Theorem
    In this section, we discuss the solution of a system of congruences having different moduli. An example of this kind of systems is the following; find a number that leaves a remainder of 1 when divided by 2, a remainder of 2 when divided by three and a remainder of 3 when divided by 5. This kind of question can be translated into the language of congruences. As a result, in this chapter, we present a systematic way of solving this system of congruences.
  • 3.5: Theorems of Fermat, Euler, and Wilson
    In this section we present three applications of congruences. The first theorem is Wilson’s theorem which states that (p−1)!+1 is divisible by p , for p prime. Next, we present Fermat’s theorem, also known as Fermat’s little theorem which states that ap and a have the same remainders when divided by p where p∤a . Finally we present Euler’s theorem which is a generalization of Fermat’s theorem and it states that for any positive integer m that is relatively prime to an integer a.

Contributors and Attributions

  • Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.


This page titled 3: Congruences is shared under a CC BY license and was authored, remixed, and/or curated by Wissam Raji.

Support Center

How can we help?