Calculate the quotient and the remainder of the Euclidean division of 123456789 by 37.

## - Congruences -

With the relation of divisibility and Euclidean division comes the notion, very simple but very useful in practice, of congruence.

## Definition 2.2.6.

Let $a$ and $a^{\prime}$ be two integers, and $b$ a non-zero natural number. We say that $a$ is congruent to $a^{\prime}$ modulo $b$, which we denote $a \equiv a^{\prime}(\bmod b)$, if $b$ divides $a-a^{\prime}$.
Obviously, we cannot parachute the solution to this exercise as we did previously. We will therefore set up the division of the integer $a=123456789$ by the integer $b=37$ as follows:

![](https://cdn.mathpix.com/cropped/2024_05_10_346641170ac76390eef3g-046.jpg?height=417&width=997&top_left_y=1679&top_left_x=541)

We conclude that the quotient and remainder sought are the integers $q=$ 3336669 and $r=36$.