Find all solutions $(x, y) \in \mathbb{N}^{2}$ of the equation: $d+\frac{x y}{d}=x+y$ where $\mathrm{d}$ is the gcd of $x$ and $y$.
There exist $x^{\prime}, y_{1} \in \mathbb{N}$ such that:

$$
\left\{\begin{array}{l}
x=d x^{\prime} \\
y=d y^{\prime} \\
x^{\prime} \text { and } y^{\prime} \text { are coprime }
\end{array}\right.
$$

The equation becomes:

$$
\begin{aligned}
1+x^{\prime} y^{\prime}=x^{\prime}+y^{\prime} & \Longleftrightarrow\left(x^{\prime}-1\right)\left(y^{\prime}-1\right)=0 \\
& \Longleftrightarrow x^{\prime}=1 \text { or } y^{\prime}=1
\end{aligned}
$$

Thus $(x, y)$ is of the form $(d, d k)$ or $(d k, d)$ with $d, k \in \mathbb{N}$.

Conversely, these pairs are indeed solutions.

## - Prime Numbers -

Definition 132 (Prime Numbers). A natural number $p>1$ is said to be prime if it has exactly two natural divisors: that is, 1 and $p$. A number that is not prime is a composite number.

Example 133. $2,3,5,7,11,13,17, \ldots$ are prime numbers but 21 is composite because $3 \mid 21$.

Theorem 134 (Fundamental Theorem of Arithmetic). Every natural number $n>1$ can be uniquely decomposed into a product of prime numbers. Therefore,

$$
n=p_{1}^{\alpha_{1}} \times \cdots \times p_{k}^{\alpha_{k}}=\prod_{i=1}^{k} p_{i}^{\alpha_{i}}
$$

where the $p_{i}$ are distinct prime numbers $p_{1}<\cdots<p_{k}$ and the $\alpha_{i}$ are strictly positive.

Example 135. The prime factorization of 60 is $60=2^{2} \times 3 \times 5$.

Theorem 136. The set of prime numbers is infinite.

Proof. Suppose, for the sake of contradiction, that there are only a finite number $n$ of prime numbers. Let these prime numbers be $p_{1}, \ldots, p_{n}$, and let $N=p_{1} p_{2} \ldots p_{n}+1$. The integer $N$ is not divisible by any of the $p_{i}$. Therefore, either it is prime, or it has a prime divisor different from $p_{1}, \ldots, p_{n}$. In either case, we obtain a contradiction.

Gauss's Lemma: Let $a, b$, and $c$ be three integers such that $a \mid b \times c$. If $a$ and $b$ are coprime, then $a \mid c$.

With what we have seen previously, this result is quite intuitive. The hypothesis $a \mid b \times c$ can be translated as the fact that we find all the elements of the prime factorization of $a$ in the product $b \times c$. But since $a \wedge b=1$, none of these elements appear in the factorization of $b$. They must therefore all come from $c$, hence the conclusion.

Example 137. Show that if two coprime integers $a$ and $b$ divide $n$, then the product $a b$ also divides $n$.

Since $a$ divides $n$, we can write $n=a k$ for some integer $k$. But then $b$ divides $a k$ and since it is coprime with $a$, it divides $k$. Thus $k=b k^{\prime}$ for some integer $k^{\prime}$ and then $n=a b k^{\prime}$, which proves that $a b$ divides $n$.

We can also see this differently: $a$ divides $n$ means that we find all the elements of the prime factorization of $a$ in $n$. Similarly, $b$ divides $n$ means that we find all the elements of the prime factorization of $b$ in $n$. Since the prime factors of $a$ and $b$ are distinct (because $a$ and $b$ are coprime), we conclude that $a b$ divides $n$.

## - Congruences -

Theorem 138 (Euclidean Division). Let $b$ be a strictly positive integer. Every integer $a$ can be uniquely written in the form $a=b q+r$, where $q$ and $r$ are integers, with $0 \leq r<b$. We call $q$ the quotient and $r$ the remainder of the Euclidean division of $a$ by $b$.

Definition 139 (Congruences). We say that $a$ and $b$ are congruent modulo $n$ and we write $a \equiv b \bmod n$ if $a$ and $b$ have the same remainder in the Euclidean division by $n$, that is, if $n$ divides $a-b$.

The congruence relation satisfies the following properties:

- if $a \equiv b \bmod n$ and $c \equiv d \bmod n$, then $a+c \equiv b+d \bmod n$,
- if $a \equiv b \bmod n$ and $c \equiv d \bmod n$, then $a c \equiv b d \bmod n$.
- if $a \equiv b \bmod n$ and $q$ is a natural number, then $a^{q} \equiv b^{q} \bmod n$.

Proofs: $a \equiv b \bmod n$ means that there exist integers $k, k^{\prime}$, and $r$ such that $a=n k+r$ and $b=n k^{\prime}+r$. Similarly, since $c \equiv d \bmod n$, there exist integers $q, q^{\prime}$, and $r^{\prime}$ such that $c=q n+r^{\prime}$ and $d=q^{\prime} n+r^{\prime}$, so $a+c=n(k+q)+\left(r+r^{\prime}\right)$ and $b+d=n\left(k^{\prime}+q^{\prime}\right)+\left(r+r^{\prime}\right)$, hence $a+c$ and $b+d$ have the same remainder modulo $n$, i.e., $a+c \equiv b+d \bmod n$. The second point is proved similarly, and the third is easily proved by induction.

Note: if $a \equiv b \bmod n$, it is not always true that $c^{a} \equiv c^{b} \bmod n$. For example, $0 \equiv 3 \bmod 3$, but $2^{0} \equiv 2^{3} \bmod 3$ is false!

Example 140. Let's show that there do not exist integers $n$ and $k$ such that $n^{2}=4 k+3$. From the equation, we have $n^{2} \equiv 3 \bmod 4$, but (we can make a table for better presentation)

- if $n \equiv 0 \bmod 4$ then $n^{2} \equiv 0 \bmod 4$
- if $n \equiv 1 \bmod 4$ then $n^{2} \equiv 1 \bmod 4$
- if $n \equiv 2 \bmod 4$ then $n^{2} \equiv 0 \bmod 4$
- if $n \equiv 3 \bmod 4$ then $n^{2} \equiv 1 \bmod 4$

it is therefore impossible that $n^{2} \equiv 3 \bmod 4$, so the proposed equation has no solution.