💡 For integers $a$ and $b$ we say that $a$ divides $b$, denoted $a|b$, if there exists an integer $c$ such that $b=ac$. In this case, $a$ is called a divisor of $b$, and $b$ is called a multiple of $a$. If $a\ne 0$ and a divisor $c$ exists it is called the quotient when $b$ is divided by $a$, and we write $c=\frac{b}{a}$ or $c=b/a$. We write $a\nmid b$ if $a$ does not divide $b$.

📖 Euclid’s Theorem: For all integers $a$ and $d\ne 0$ there exist unique integers $q$ and $r$ satisfying

$$a=dq+r\text{and}0\le r<|d|.$$

Hence $a$ is called the dividend, $d$ is called the divisor, $q$ is called the quotient, and $r$ is called the remainder. The remainder $r$ is often denoted as $R_d(a)$ or sometimes as $a\text{mod}d$.

💡 For integers $a$ and $b$ (not both 0), an integer $d$ is called a greatest common divisor of $a$ and $b$ if $d$ divides both $a$ and $b$ and if every common divisor of $a$ and $b$ divides $d$, i.e., if

$$d|a\wedge d|b\wedge \forall c((c|a\wedge c|b)\to c|d).$$

💡 For $a,b\in \mathbb{Z}$ (not both 0) one denotes the unique positive greatest common divisor by $\text{gcd}(a,b)$ and usually calls it the greatest common divisor. If $\text{gcd}(a,b)=1$, then $a$ and $b$ are called relatively prime.

📌 For any integers $m$, $n$ and $q$, we have

$$\text{gcd}(m,n-qm)=\text{gcd}(m,n).$$

💡 The above lemma implies in particular that

$$\text{gcd}(m,R_m(n))=\text{gcd}(m,n)$$

which is the basis for Euclid’s well-known $\text{gcd}$-algorithm: Start with $m<n$ and repeatedly replace the pair $(m,n)$ by the pair $(R_m(n),m)$ until the remainder is 0, at which point the last non-zero number is equal to $\text{gcd}(m,n)$.

💡 For $a,b\in \mathbb{Z}$, the ideal generated by $a$ and $b$, denoted by $(a,b)$, is the set

$$(a,b):=\{ua+vb|u,v\in \mathbb{Z}\}.$$

Similarly, the ideal generated by a single integer $a$ is

$$(a):=\{ua|u\in \mathbb{Z}\}.$$

📌 For $a,b\in \mathbb{Z}$ there exists $d\in \mathbb{Z}$ such that $(a,b)=(d)$.

📌 Let $a,b\in \mathbb{Z}$ (not both 0). If $(a,b)=(d)$, then $d$ is a greatest common divisor of $a$ and $b$.

📎 For $a,b\in \mathbb{Z}$ (not both 0), there exist $u,v\in \mathbb{Z}$ such that

$$\text{gcd}(a,b)=ua+vb.$$

💡 The least common multiple $l$ of two positive integers $a$ and $b$, denoted $l=\text{lcm}(a,b)$, is the common multiple of $a$ and $b$ which divides every common multiple of $a$ and $b$, i.e.,

$$a|l\wedge b|l\wedge \forall m((a|m\wedge b|m)\to l|m).$$

💡 A positive integer $p>1$ is called prime if the only positive divisors of $p$ are 1 and $p$. An integer greater than 1 that is not a prime is called composite.

📖 The fundamental theorem of arithmetic: Every positive integer can be writter uniquely (up to the order in which factors are listed) as the product of primes.

📌 If $p$ is a prime which divides the product $x_1{x}_2\dots x_n$ of some integers $x_1,\dots ,x_n$, then $p$ divides one of them, i.e., $p|x_i$ for some $i\in \{1,\dots ,n\}$.

💡 Expressing $\text{gcd}$ and $\text{lcm}$: The fundamental theorem of arithmetic assures that integers $a$ and $b$ can be written as

$$a=\prod _i{p}_i^{e_i}\text{and}b=\prod _i{p}_i^{f_i}.$$

This product can be understood in two different ways. Either it is over all primes where all but finitely many of the $e_i$ are 0, or it is over a fixed agreed set of primes. Either view is correct. Now we have

$$\text{gcd}(a,b)=\prod _i{p}_i^{\text{min}(e_i,f_i)}$$

and

$$\text{lcm}(a,b)=\prod _i{p}_i^{\text{max}(e_i,f_i)}.$$

It is easy to see that

$$\text{gcd}(a,b)\cdot \text{lcm}(a,b)=ab$$

because for all $i$ we have

$$\text{min}(e_i,f_i)+\text{max}(e_i,f_i)=e_i+f_i.$$

📖 $\ast \sqrt{n}$ is irrational unless $n$ is a square ($n=c^2$ for some $c\in \mathbb{Z}$).*

📖 There are infinitely many primes.

📖 Gaps between primes can be arbitrarily large, i.e., for every $k\in \mathbb{N}$ there exists $n\in \mathbb{N}$ such that the set $\{n,n+1,\dots ,n+k-1\}$ contains no prime.

💡 The prime counting function $\pi :\mathbb{R}⟶\mathbb{N}$ is defined as follows: For any real $x$, $\pi (x)$ is the number of primes $\le x$.

📖 $\underset{x\to \infty }{\lim }\frac{\pi (x)\ln (x)}{x}=1$.

❓ Conjecture: There exist infinitely many twin primes, i.e., primes $p$ for which also $p+2$ is prime.

❓ Goldbach’s Conjecture: Every even number greater than 2 is the sum of two primes.

📌 Every composite integer $n$ has a prime divisor $\le \sqrt{n}$.

💡 For $a,b,m\in \mathbb{Z}$ with $m\ge 1$, we say that $a$ is congruent to $b$ modulo $m$ if $m$ divides $a-b$. We write $a\equiv b(\text{mod}m)$ or simply $a{\equiv }_{m}b$, i.e.,

$$a{\equiv }_{m}b\stackrel{\mathrm{def}}{⟺}m|(a-b).$$

📌 For any $m\ge 1$, ${\equiv }_m$ is an equivalence relation on $\mathbb{Z}$.

💡 $a{\cancel{\equiv }}_{m}b⟹a\ne b.$

📌 If $a{\equiv }_{m}b$ and $c{\equiv }_{m}d$, then

$$a+c{\equiv }_{m}b+d\text{and}ac{\equiv }_{m}bd.$$

📎 Let $f(x_1,\dots ,x_k)$ be a multi-variate polynomial in $k$ variables with integer coefficients, and let $m\ge 1$. If $a_i{\equiv }_m{b}_i$ for $1\le i\le k$, then

$$f(a_1,\dots ,a_k){\equiv }_{m}f(b_1,\dots ,b_k).$$

📌 For any $a,b,m\in \mathbb{Z}$ with $m\ge 1$,

1. $a{\equiv }_m{R}_m(a).$
2. $a{\equiv }_{m}b⟺R_m(a)=R_m(b).$

📎 Let $f(x_1,\dots ,x_k)$ be a multi-variate polynomial in $k$ variables with integer coefficients, and let $m\ge 1$. Then

$$R_m(f(a_1,\dots ,a_k))=R_m(f(R_m(a_1),\dots ,R_m(a_k))).$$

📌 The congruence equation

$$ax{\equiv }_{m}1$$

has a solution $x\in {\mathbb{Z}}_m$ if and only if $\text{gcd}(a,m)=1$. The solution is unique.

💡 If $\text{gcd}(a,m)=1$, the unique solution $x\in {\mathbb{Z}}_m$ to the congruence equation $ax{\equiv }_{m}1$ is called the multiplicative inverse of $a$ modulo $m$. One also uses the notation $x{\equiv }_m{a}^{-1}$ or $x{\equiv }_{m}1/a$.

📖 The Chinese Remainder Theorem (CRT): Let $m_1,m_2,\dots ,m_r$ be pairwise relatively prime integers and let $M={\prod }_{i=1}^r{m}_i$. For every list $a_1,\dots ,a_r$ with $0\le a_i\le m_i$ for $1\le i\le r$, the system of congruence equations

$$\begin{gathered} x{\equiv }_{m_1}{a}_1 \\ x{\equiv }_{m_2}{a}_2 \\ \dots \\ x{\equiv }_{m_r}{a}_r \end{gathered}$$

for $x$ has a unique solution $x$ satisfying $0\le x\le M$.

💡 Useful theorems involving modular arithmetic:

• For any $a,e,m,n\in \mathbb{N}\setminus \{0\}$: $R_m(a^e)=1⟹R_m(a^n)=R_m(a^{R_e(n)})$.