## 4.1 Introduction to Congruence

In Linear Congruence Equations (Fundamental Concepts and Principles)“, the author takes the reader on a comprehensive tour of linear congruence equations and their many applications. The book is ideal for students who want to deepen their knowledge of mathematics as well as professionals who need to use linear congruence equations in their work. It provides a clear and concise explanation of the concepts underlying linear congruence equations, making it an essential resource for anyone looking to understand this important topic.

Congruence in the integers means that two numbers are equivalent if their difference is a multiple of a certain number, called the modulus. In other words, we can say that two numbers are congruent modulo m if they have the same remainder when divided by m. For example, 17 and 29 are Congruent modulo 4 because the remainders when we divide them by 4 are 1 and 1 respectively.

Congruence is an equivalence relation, which means that it satisfies the three properties of reflexivity, symmetry, and transitivity. There are also several lemmas about congruence which we will now state without proof. The first one says that if a is congruent to b modulo m and c is congruent to d modulo m then a+c is congruent to b+d modulo m.

The second lemma states that if a is congruent to b modulo m and c is any integer then a+c is congruent to b+c modulo m. The third and final lemma says that if a is congruent to b modulo m then ac is congruent to bc modulo m. These lemmas show that congruent behaves nicely with addition, subtraction, and multiplication and so it should be clear why it is such a useful concept.

Modular arithmetic is a system that involves the remainders of the division of certain numbers. It is often referred to as “clock arithmetic” because of its similarity to how hours are measured on a clock. The numbers in modular arithmetic are called “objects” and the remainders are called “residues”. The concept of modular arithmetic can be difficult to grasp at first, but it is actually quite simple.

In many applications, it is important to know not only the value of x modulo n, but also its least positive residue. For example, in computer science, when working with very large numbers that are too large to fit into a single data type, it is often necessary to store only the least significant digits of the number; and when performing arithmetic operations on such numbers, it is often necessary to reduce them modulo some number n that is a power of two (such as 216 = 65536), so that they can be stored in a smaller data type. In both cases, it suffices to know only the least positive residue of x modulo n.

In this chapter, we explain what congruence (modular arithmetic) is in the integers. We also provide some examples to illustrate how it works. Least positive residues are an important part of understanding modular arithmetic. We hope that by the end of this chapter, you will have a good understanding of both least positive residues and congruence in the integers.

In mathematics, modular arithmetic is a system that allows numbers to be divided into congruent classes. This means that the remainders of two numbers when divided by a third number are the same. For example, when we divide 7 by 3, the remainder is 1; when we divide 8 by 3, the remainder is 2; and when we divide 9 by 3, the remainder is 0. In modular arithmetic, these three numbers would be said to be congruent modulo 3.

Modular arithmetic is particularly useful in computer science because it can be used to represent data in a more efficient way. For example, instead of storing the full date (December 21st, 2015), a computer can store just the day of the month (21) and the year (2015). This is possible because we know that there are only 31 days in December, so the modular arithmetic system allows us to store the information more efficiently.

Overall, modular arithmetic is a powerful tool that can be used in a variety of ways. It is particularly useful for computer science applications, but it can also be used for other purposes as well.

In this chapter, we will explain what congruence (modular arithmetic) in the integers is and how it works.

Linear congruence is an equation that produces a set of integers that are evenly spaced apart. The equation has the form $$ab \equiv 1 \pmod{n}$$, where a, b, and n are integers and n > 0. Linear congruence equations are very powerful tools that can be used to solve various mathematical problems. In fact, they are so versatile that they have even been used to crack codes!

One way to solve for x is to find the modular inverse of a modulo m. This can be done using the Extended Euclidean Algorithm. Once the modular inverse is found, it can be plugged into the equation to solve for x.

The Euclidean algorithm is a fast and straightforward way to solve these equations. Given an equation $$ax \equiv b \pmod{m}$$, we can use the Euclidean algorithm to find a solution in just a few steps. First, we find the greatest common divisor of a and m using the Euclidean algorithm. Then, we divide b by this greatest common divisor to get an integer c. Finally, we use the Extended Euclidean algorithm to find a number d such that $$ad \equiv 1 \pmod{m}$$. Plugging in these values for x in our original equation gives us the solution: $$x \equiv cd \pmod{m}$$. By using the Euclidean algorithm, we can quickly and easily solve linear congruence equations.

Linear congruence equations are a powerful tool that can be used to solve many different types of problems. With a little practice, anyone can learn how to use them.

These equations have a solution if and only if a and m are relatively prime. If an equation has a solution, then all solutions can be found by repeated addition of m to any one solution. In particular, if x is a solution of the equation, then so are x + km for any integer k. The set of all solutions of the equation is called the residue class of x (modulo m).

In this chapter, you’ll learn that two numbers in the same residue class modulo m give the same remainder when divided by m. For example, 7 and 17 are in the same residue class modulo 6 because they both leave the same remainder, 1, when divided by 6. On the other hand, 14 is not in this residue class because it leaves a different remainder, 2, when divided by 6.

Linear Congruence Equations are useful in many situations, including finding the inverse of an integer with modular arithmetic. If we have an integer a such that there is no integer b for which $$ab \equiv 1 \pmod{m}$$, then there is no inverse of a (modulo m). However, if $$ab \equiv 1 \pmod{m}$$, then a has an inverse modulo m, and this inverse is given by b.

Thus, to find the inverse of an integer with modular arithmetic, we must first determine whether or not it has an inverse. We can do this by solving a linear congruence equation. In summary, in this chapter, you’ll learn that linear congruence equations are both necessary and sufficient for finding the inverse of an integer with modular arithmetic.

This book is a comprehensive guide to understanding linear congruence equations and their various applications. It is ideal for students who are looking to further their knowledge of mathematics and for professionals who need to use linear congruence equations in their work. The author takes the reader on a clear and concise tour of the concepts underlying linear congruence equations, making it an essential resource for anyone looking to understand this important topic. I highly recommend this book to anyone interested in learning more about linear congruence equations.

## 4.2 Introduction to Congruence

A modern treatment of congruences was introduced by Karl Friedrich Gauss. Congruence, or modular arithmetic, arises naturally in common everyday situations. For example, odometers usually work modulo 100,000 and utility meters often operate modulo 1000. In trigonometry, it is common to work in degrees, that is modulo 360 degrees, and indeed, it is common to work in minutes and seconds both of which are working modulo 60.

Definition 4.1 Let $$n$$ be a positive integer. Integers $$a$$ and $$b$$ are congruent modulo $$n$$ if $$a-b$$ is divisible by $$n$$ and is denoted by $$a \equiv b \pmod{n}.$$

Notice $$24\equiv 4 \pmod{5}$$ since $$5|(24-4)$$ but $$24 \not\equiv 3 \, \pmod{5}$$ since $$5\mid (24-3)$$ does not hold. Also, $$111\equiv 9 \pmod{40}$$ since $$40|(111-9)$$ and $$111\not\equiv 8 \pmod{40}$$ since $$40\mid (111-8)$$ does nto hold.

Next we show that congruence modulo $$n$$ is an equivalence relation on the set of integers.

Theorem 4.1 For each positive integer $$n$$, congruence modulo $$n$$ is an equivalence relation on the set of integers.

Proof. If $$a$$ is an integer, then $$a\equiv a \pmod{n}$$ since $$n|(a-a)$$ and so $$\equiv$$ is reflexive. If $$a$$ and $$b$$ are integers and $$a\equiv b \pmod{n},$$ then $$b\equiv a \pmod{n}$$ since $$n|(b-a)$$ $$\Longleftrightarrow$$ $$n|(a-b)$$ and so the relation $$\equiv$$ is symmetric. If $$a, b$$ and $$c$$ are integers, $$a\equiv b \pmod{n},$$ and $$b\equiv c \pmod{n},$$ then $$a\equiv c \pmod{n}$$ because $$n|(b-a)$$ and $$n|(c-b)$$ implies $$n|(a-c)$$ and so the relation $$\equiv$$ is also transitive.

Theorem 4.2 If $$a$$ and $$b$$ are integers, then $$a\equiv b \pmod{n}$$ if and only if there exists an integer $$k$$ such that $$a=b+k n.$$

Proof. If $$a\equiv b \pmod{n},$$ then $$n|(a-b)$$ and this means there exists an integer $$k$$ such that $$k n=a-b$$ and so $$a=b+k n.$$ Conversely, if there is an integer $$k$$ such that $$a=b+k n,$$ then $$n|(a-b)$$; and so $$a\equiv b \pmod{n}.$$

Lemma 4.1 For all integers $$a$$, $$b$$, $$c$$, and $$d$$, if $$a\equiv c \pmod{n}$$ and $$b\equiv d \pmod{n},$$ then $$a\pm b\equiv c\pm d \pmod{n}$$ and $$a b\equiv c d \pmod{n}.$$

Proof. If $$a\equiv c \pmod{n}$$ and $$b\equiv d \pmod{n},$$ then $$n|a-c$$ and $$n|b-d.$$ It follows that, $$n|(a\pm b)-(c\pm d)$$ and thus $$a\pm b\equiv c\pm d \pmod{n}.$$ It also follows that, $$n|(a b-c b)$$ and $$n|(c b-c d);$$ thus $$n|(a b-c d).$$ Therefore, $$a b\equiv c d \pmod{n}.$$

Lemma 4.2 For all integers $$a$$, $$c$$, and $$d$$, if $$a+c\equiv a+d \pmod{n},$$ then $$c\equiv d \pmod{n}.$$

Proof. If $$a+c\equiv a+d \pmod{n},$$ then $$n|(a+c)-(a+d)$$ and so $$n|c-d$$ which means $$c\equiv d \pmod{n}.$$

Lemma 4.3 For all integers $$a$$, $$c$$, and $$d$$, if $$a c\equiv a d \pmod{n}$$ and $$(a,n)=1,$$ then $$c\equiv d \pmod{n}.$$

Proof. If $$a c\equiv a d \pmod{n},$$ then $$n|(a c-a d)$$ which means $$n|a(c-d).$$ Since $$(a,n)=1,$$ it follow that $$n|(c-d)$$ and so $$c\equiv d \pmod{n}.$$

Lemma 4.4 For all integers $$a$$, there exists an integer $$h$$ such that $$a h\equiv 1 \pmod{n}$$ if and only if $$(a,n)=1.$$

Proof. If $$(a,n)=1,$$ then there exists integers $$s$$ and $$t$$ such that $$s a+t n=1.$$ Let $$h=s,$$ then $$a h\equiv 1 \pmod{n}$$ as desired. Conversely, if there is such a $$h$$ then $$a h=1+q n$$ for some $$q.$$ Thus, $$a h+(-q) n=1$$ and so $$(a,n)=1.$$

Lemma 4.5 For all integers $$a$$, $$b$$, and $$c$$, if $$a c\equiv b c \pmod{n},$$ then $$a\equiv b \pmod{n/(c,n)}.$$

Proof. If $$a c\equiv b c \pmod{n},$$ we know that $$n|(a c-b c)=c(a-b).$$ Thus there exists an integer $$k$$ such that $$c(a-b)=k n$$ and dividing both sides by $$d=(c,n),$$ we have $$(c/d)(a-b)=k(n/d).$$ Because $$(n/d,c/d)=1$$ it follows that $$(n/d)|(a-b).$$ Therefore, $$a\equiv b \pmod{n/(c,n)}.$$

Lemma 4.6 For all integers $$a$$ and $$b$$, if $$k,n>0$$ and $$a\equiv b \pmod{n},$$ then $$a^k\equiv b^k \pmod{n}.$$

Proof. Because $$a\equiv b \pmod{n}$$ we have by definition, $$n|(a-b)$$ and since $a^k-b^k=(a-b)\left(a^{k-1}+a^{k-2}b+\cdot \cdot \cdot +a b^{k-2}+b^{k-1}\right)$ we see that $$(a-b)\left|\left(a^k-b^k\right)\right.;$$ whence $$n\left|\left(a^k-b^k\right).\right.$$ Therefore, $$a^k\equiv b^k$$ $$\pmod{n}.$$

Definition 4.2 Given a modulus $$n$$ and an integer $$a$$ the least positive residue of $$a$$ modulo $$n$$ is the smallest positive integer $$r$$ such that $$a\equiv r \pmod{n}.$$

For example, the remainder of $$n$$ when divided by 9 is the same as the remainder of the sum of its digits when divided by 9 which follows from writing $$n=d_t10^t+d_{t-1}10^{t-1}+\ldots +d_110+d_0$$ where $$0\leq d_i\leq 9$$ by noting that $$10^k\equiv 1 \pmod{9}$$ for any $$k.$$ Notice also that the remainder of $$n$$ when divided by 11 is the same as the remainder of the alternating sum of its digits when divided by 11 which follows from writing $$n$$ in decimal form and noting that $$10^k\equiv (-1)^k \pmod{11}$$ for any $$k.$$

Let $$\{0,1,2, ... ,n-1\}$$ be a complete set of on $$\mathbb{Z}$$ for congruence modulo $$n,$$ then define $$\mathbb{Z}_n\text{:=}\{[1],[2],[3], ... ,[n-1]\}$$ and define the operation $$+$$ on $$\mathbb{Z}_n$$ by $$[a]+[b]=[a+b].$$ Arithmetic using this operation is referred to as equivalence class representatives} on $$\mathbb{Z}$$ for congruence modulo $$n,$$ then define $$\mathbb{Z}_n\text{:=}\{[1],[2],[3], ... ,[n-1]\}$$ and define the operation $$+$$ on $$\mathbb{Z}_n$$ by $$[a]+[b]=[a+b].$$ Arithmetic using this operation is referred to as \index{modular arithmetic .

The operation $$+$$ is a well-defined binary operation; meaning, if $$[a]=[b]$$ and $$[c]=[d]$$ in $$\mathbb{Z}_n$$, then $$[a]+[b]=[a+b]=[c+d]=[c]+[d]$$ which follows from $$a\equiv b \pmod{n}$$ and $$c\equiv d \pmod{n} \Rightarrow a+c\equiv b+d \pmod{n}.$$ For example, the arithmetic tables for $$\mathbb{Z}_{6}$$ are \begin{align*} \renewcommand{\arraystretch}{1} \begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \end{array} & & \renewcommand{\arraystretch}{1} \begin{array}{c|cccccc} \times & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 4 & 1 & 2 \\ 4 & 0 & 4 & 2 & 0 & 1 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \end{array} \end{align*}

Theorem 4.3 Let $$n$$ be a positive integer, then $$+$$ is associative and commutative, each element has an inverse, and $$[0]$$ is the identity element.

Proof. By the definition of $$+$$ and the use of associativity in the integers, it follows that \begin{align*} [a]+([b]+[c])& =[a]+[b+c] =[a+(b+c)]=[(a+b)+c] \\ &=[a+b]+[c]=([a]+[b])+[c] \end{align*} for any $$[a],$$ $$[b],$$ and $$[c]\in \mathbb{Z}_n.$$ The element $$[0]$$ is the identity because $[a]+[0]=[a+0] [a]$ for any $$[a]\in \mathbb{Z}_n.$$ For every element $$[a]$$ of $$\mathbb{Z}_n$$ there is an inverse because $[a]+[-a] =[a+(-a)]=[0]$ and indeed $$[-a]\in \mathbb{Z}_n.$$ Commutativity follows since $[a]+[b]=[a+b]=[b+a]=[b]+[a]$ for $$[a],$$ $$[b]\in \mathbb{Z}_n.$$

Theorem 4.4 Let $$n$$ be a positive integer. Then a complete set of equivalence class representatives on $$\mathbb{Z}$$ for congruence modulo $$n$$ is $$\{0,1,2, ... ,n-1\}.$$

Proof. Given an integer $$x,$$ the Division Algorithm yields unique integers $$q$$ and $$r$$ such that $$x=n q+r$$ and $$0\leq r<n.$$ Then $$x\equiv r \pmod{n}$$ and so $$x$$ is congruent to at least one of $$\{0,1,2,\text{..},n-1\}.$$ In fact $$r$$ is unique because otherwise, say $$x\equiv s \pmod{n}$$ and $$x=n t+s$$ with $$0\leq s<n$$ for some $$t,$$ would contradict the uniqueness of the Division Algorithm.

## 4.3 Linear Diophantine Equations

In the following Diophantine equations, $$x$$, $$y$$, and $$z$$ are the unknowns and the other letters are given constants.

$$$ax+by=1$$$

This is a linear Diophantine equation.

$$$x^n+y^n=z^n$$$

For n = 2 there are infinitely many solutions (x,y,z): the Pythagorean triples. For larger integer values of n, Fermat’s Last Theorem states there are no positive integer solutions $$(x, y, z)$$.

$$$x^2-ny^2=\pm 1$$$

This is Pell’s equation, which is named after the English mathematician John Pell. It was studied by Brahmagupta in the 7th century, as well as by Fermat in the 17th century.

$$$\frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}$$$

The Erdos-Straus conjecture states that, for every positive integer n ? 2, there exists a solution in x, y, and z, all as positive integers. Although not usually stated in polynomial form, this example is equivalent to the polynomial equation $$4xyz = yzn + xzn + xyn = n(yz + xz + xy)$$.

The term Diophantine equation usually refers to any equation in one or more unknowns that is to be solved in the integers.

The simplest kind of Diophantine equation is the linear Diophantine equation , namely $$a x + b y = c$$. In general, Diophantine equations furnish a natural vehicle for puzzles and problems of a mathematical nature.

Theorem 4.5 (Linear Diophantine Equation) The linear Diophantine equation $$a x+b y=c$$ has a solution if and only if $$d|c,$$ where $$d=(a,b).$$ Moreover, if $$\left(x_0,y_0\right)$$ is a solution, then the set of solutions of the equation consists of pairs $$(x,y)$$ where

$$$\label{ldequ} x=x_0+\frac{t b}{d} \qquad \text{and} \qquad y=y_0-\frac{t a}{d}$$$

and $$t$$ is an arbitrary integer.

Proof. Since $$d=(a,b)$$ there exists integers $$m$$ and $$n$$ such that $$a m+b n=d$$. Since $$d|c$$ we have an integer $$k$$ such that $$c=d k$$ and thus we have $$(a m+b n)k=d k$$. Thus, $$a (m k)+b (n k)=c$$ and so we have a solution. Conversely, suppose $$a x+b y=c$$ has a solution say $$x_1$$ and $$y_1.$$ Then $$a x_1+b y_1=c$$ and since $$d|a$$ and $$d|b$$ we have $$d|c.$$ Let $$x_0$$ and $$y_0$$ be any solution. Then we have $$a x_0+b y_0=c$$ and so
$a x_0+\frac{t a b}{d}+b y_0-\frac{t a b}{d}=c$ for any integer $$t.$$ Therefore, $$\ref{ldequ}$$ holds for any integer $$t.$$

It remains to show that all solutions $$(x,y)$$ have the correct form. Let $$(x,y)$$ be an arbitrary solution and let $$\left(x_0,y_0\right)$$ be any particular solution. Then we have $$a\left(x-x_0\right)+b\left(x-x_0\right)=0$$ and thus $$a\left(x-x_0\right)=b\left(y_0-y\right).$$ Now enter $$d$$. Dividing by $$d,$$ we have
$\frac{a}{d}\left(x-x_0\right)=\frac{b}{d}\left(y_0-y\right).$ Observe that $\left(\frac{a}{d},\frac{b}{d}\right)=1$ and so $$\frac{a}{d}\mid \left(y_0-y\right)$$. Therefore, there exists an integer $$s$$ such that $$y=y_0-\left(\frac{a}{d}\right)s$$ and by substitution, $$x=x_0+\left(\frac{b}{d}\right)s$$ as desired.

While solving linear Diophantine equations are straightforward, this is not true for general Diophantine equations. In 1900, in recognition of their depth, David Hilbert proposed the solvability of all Diophantine problems as the tenth of his celebrated problems. In 1970, a novel result in mathematical logic known as Matiyasevich’s theorem settled the problem negatively: in general Diophantine problems are unsolvable.

Using $$\ref{lindiothm}$$ we can check if a linear Diophantine equations is solvable and if solvable, actually find its solutions. The key ingredient is finding a particular solution is the Euclidean algorithm.

Example 4.1 Solve the linear Diophantine equation $$14x+34y=90.$$

Solution. Since $$(14,34)=2$$ and $$2|90.$$ There is a solution and they are all given by $$\ref{ldequ}$$ and so we need to find an initial solution. Since an initial solution is $$x=4$$ and $$y=1$$ we have all solutions $x=4+17 t$ and $$y=1-7 t$$ where $$t\in\mathbb{Z}$$.

Example 4.2 Solve the linear Diophantine equation $$14x+35x=91.$$

Solution. Since $$(14,35)=7$$ and $$7|91$$ the equation is solvable.
Since an initial solution is $$x=4$$ and $$y=1$$ we have all solutions $$x=4+2t$$ and $$y=1-5t$$ where $$t\in\mathbb{Z}$$.

Example 4.3 Solve the linear Diophantine equation $$14x+36y=93.$$

Solution. Since $$(14,36)=2$$ and $$2\nmid 93$$ there are no solution to the linear Diophantine equation $$14x+36y=93.$$.

Corollary 4.1 If $$(a,b)=1$$ and if $$x_0$$ and $$y_0$$ is a particular solution of the linear Diophantine equation $$a x+b y=c,$$ then all solutions are given by $$x=x_0+b t$$ and $$y=y_0-a t$$ for integral values of $$t.$$

Proof. The proof follows mediately from $$\ref{lindiothm}$$.

For example, the equation $$5x+22y=18$$ has $$x_0=8,$$ $$y_0=-1$$ as one solution and so a complete solution is given by $$x=8+22t$$ and $y=-1-5t$ for arbitrary integral values of $$t.$$

A problem in Diophantus’ Arithmetica is to find four natural numbers whose sums by three are 20, 22, 24, and 27. Can you find these four integers?

Theorem 4.6 (General Linear Diophantine Equation) If $$a_1,a_2,\ldots ,a_n$$ are nonzero positive integers, then the equation $a_1x_1+ \cdots +a_nx_n=c$ has an integral solution if and only if $$d=\left(a_1,\ldots ,a_n\right)$$ divides $$c.$$ Furthermore, when there is a solution, there are infinitely many solutions.

Proof. The proof is left for the reader.

Example 4.4 Which combinations of pennies, dimes, and quarters have a total value of $$99$$ cents.

Diophantus made important advances in mathematical notation, becoming the first person known to use algebraic notation and symbolism. Before him everyone wrote out equations completely. Diophantus introduced an algebraic symbolism that used an abridged notation for frequently occurring operations, and an abbreviation for the unknown and for the powers of the unknown.

Solution. Let $$x,y,$$ and $$z$$ be the number of pennies, dimes, and quarters, respectively. To solve this question we will solve the linear Diophantine equation: $$x+10y+25z=99.$$ Since $$x,y,$$ and $$z$$ are all positive integers, it follows that $$z=0,1,2,3;$$ and so we can solve the 4 corresponding equations in only $$x$$ and $$y.$$ First, we solve $$x+10y=99.$$ Clearly, $$x_0=99$$ and $$y_0=0$$ is a particular solution and since $$(1,10)=1$$ all solutions are given by $$x=99+10t$$ and $$y=0-t.$$ By letting $$t$$ range from 0 to $$-9$$, we find some combinations of pennies, dimes, and quarters that total 99 cents:

$\begin{array}{c|cccccccccc} x & 99 & 89 & 79 & 69 & 59 & 49 & 39 & 29 & 19 & 9 \\ \hline y & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline z & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline t & 0 & -1 & -2 & -3 & -4 & -5 & -6 & -7 & -8 & -9 \end{array}$

Next, we solve $$x+10y=74.$$ Clearly, $$x_0=74$$ and $$y_0=0$$ is a particular solution and since $$(1,10)=1$$ all solutions are given by $$x=74+10t$$ and $$y=0-t.$$ By letting $$t$$ range from 0 to $$-7$$, we find more combinations of pennies, dimes, and quarters that total 99 cents:

$\begin{array}{c|cccccccc} x & 74 & 64 & 54 & 44 & 34 & 24 & 14 & 4 \\ \hline y & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline z & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline t & 0 & -1 & -2 & -3 & -4 & -5 & -6 & -7 \end{array}$

Next, we solve $$x+10y=49.$$ Clearly, $$x_0=49$$ and $$y_0=0$$ is a particular solution and since $$(1,10)=1$$ all solutions are given by $$x=49+10t$$ and $$y=0-t.$$ By letting $$t$$ range from 0 to $$-4$$, we find more combinations of pennies, dimes, and quarters that total 99 cents:

$\begin{array}{c|ccccc} x & 49 & 39 & 29 & 19 & 9 \\ \hline y & 0 & 1 & 2 & 3 & 4 \\ \hline z & 2 & 2 & 2 & 2 & 2 \\ \hline t & 0 & -1 & -2 & -3 & -4 \end{array} \hspace{1cm} \begin{array}{c|ccc} x & 24 & 14 & 4 \\ \hline y & 0 & 1 & 2 \\ \hline z & 2 & 2 & 2 \\ \hline t & 0 & -1 & -2 \end{array}$

Finally, we solve $$x+10y=24.$$ Clearly, $$x_0=24$$ and $$y_0=0$$ is a particular solution and since $$(1,10)=1$$ all solutions are given by $$x=49+10t$$ and $$y=0-t.$$ By letting $$t$$ range from 0 to $$-2$$, we find even more combinations of pennies, dimes, and quarters that total 99 cents.

## 4.4 Exercises

Exercise 4.1 Solve the linear Diophantine equation by either finding all solutions or by showing there are none.

• $$3x+4y=7$$
• $$17x+13y=100$$
• $$30x+47y=-11$$
• $$25x+95y=970$$
• $$102x+1001y=1$$
• $$7x+21 y+35z=8.$$
• $$6x+51y=22$$
• $$33x+14y=115$$
• $$14x+35y=93$$
• $$56x+72y=40$$
• $$24x+138y=18$$
• $$221x+35y=11$$
• $$18x+5y=48$$
• $$54x+21y=906$$
• $$158x-57y=7$$
• $$41x-51y=223$$

Exercise 4.2 Solve the linear Diophantine equation $7101x+102y+103z=1$ by either finding all solutions or by showing there are none.

Exercise 4.3 A grocer order apples and oranges at a total cost of $$\ 8.39.$$ If apples cost him $$25$$ cents each and oranges cost him 18 cents each, how many of each type of fruit did he order?

Exercise 4.4 A postal clerk has only $$14$$ cents and $$21$$ cent stamps to sell. What combination of these may be used to mail a package requiring postage of exactly $$$4.00.$$ Exercise 4.5 Divide 100 into two summands such that one is divisible by 7 and the other by 11. Exercise 4.6 Is it possible to have 50 coins, all of which are pennies, dimes, or quarters, with a total worth 3 dollars. Exercise 4.7 When Mr. Smith cached a check at his bank, the teller mistook the number of cents for the number of dollars and vice versa. Unaware of this, Mr. Smith spent 68 cents and then noticed to his surprise that he had twice the amount of the original check. Determine the smallest value for which the check could have been written. Exercise 4.8 Divide 100 into two summands such that one is divisible by 7 and the other by 11. Exercise 4.9 A man has 5 diamonds, 8 rubies, 7 sapphires, and 83 gold coins; a second man has 7,9,6, and 74 of these items, respectively; a third man has 3, 13, 11, and 80. If the collections are considered equally valuable, how many gold coins is each diamond, ruby, and sapphire writ? Exercise 4.10 Solve the linear Diophantine equation, $$714x+7007y=7.$$ Exercise 4.11 Solve the linear Diophantine equation by either finding all solutions or by showing there are none for $$17x+13y=100.$$ Exercise 4.12 Solve the linear congruence $$5x\equiv 7 (\text{mod} 57)$$ using basic properties of congruence (no linear Diophantine equation). Show all your steps. Exercise 4.13 Explain why the linear Diophantine equation $$2x-101y=82$$ is solvable or not solvable. If possible find all solutions. Exercise 4.14 Solve the linear congruence $$5x\equiv 15 (\text{mod} 35)$$ by solving a linear Diophantine equation. Show all your steps. Exercise 4.15 Solve the congruence $$3x\equiv 5 (\text{mod} 16)$$ by writing a linear Diophantine equation and solving it. Exercise 4.16 Show that the sum of two even or two odd integers is even and also show that the sum of an odd and an even is odd. Exercise 4.17 Show that the product of two odd integers is odd and also show that the product of two integers is even if either or one of them is even. Exercise 4.18 Show that if $$a$$ and $$b$$ are positive integers and $$a|b,$$ then $$a\leq b.$$ Exercise 4.19 Show that if $$a$$ is an integer, then $$3$$ divides $$a^3-a.$$ Exercise 4.20 Show that the square of every of odd integer is of the form $$8k+1.$$ Exercise 4.21 Show that the product of every two integers of the form $$6k+5$$ is of the form $$6k+1.$$ Exercise 4.22 Find the number of positive integers not exceeding 1000 that are divisible by 3 but not by 4. Exercise 4.23 Show that any integer of the form $$6k+5$$ is also of the form $$3 j+2,$$ but not conversely. Exercise 4.24 Prove that if $$a$$ ad $$b$$ are integers, with $$b>0$$, then there exists unique integers $$q$$ and $$r$$ satisfying $$a=bq+r$$, where $$2b\leq r <3b$$. Exercise 4.25 Extend the Division Algorithm by allowing negative divisors. Specifically, prove that whenever $$a$$ and $$b\neq 0$$ are integers, there are unique integers $$q$$ and $$r$$ such that $$a=bq+r$$, where $$0\leq r <|b|$$. Exercise 4.26 Prove that the square of any integer is either of the form $$3k$$ or $$3k+1$$. Exercise 4.27 Prove that the cube of any integer has one of the forms: $$9k$$, $$9k+1$$, $$9k+8$$. Exercise 4.28 Prove that the cube of any integer has one of the forms: $$7k$$, $$7k+1$$, $$7k-1$$. Exercise 4.29 Prove that the fourth power of any integer is either of the form $$5k$$ or $$5k+1$$. Exercise 4.30 Let $$a$$ and $$b$$ be positive integers. Prove if $$a|b,$$ then $$a^n|b^n$$ for any positive integer $$n.$$ Exercise 4.31 Use mathematical induction to show that $$n^5-n$$ is divisible by 5 for every positive integer $$n.$$ Exercise 4.32 Prove that if $$a$$, $$b$$, and $$c$$ are integers with $$a$$ and $$c$$ nonzero, such that $$a|b$$ and $$c|d$$, then $$ac|bd$$. Exercise 4.33 Prove or disprove with a counterexample. There are integers $$a$$, $$b$$, and $$c$$ such that $$a|bc$$, but $$a\nmid b$$ and $$a\nmid c$$. Exercise 4.34 Prove or disprove with a counterexample. If $$a$$, $$b$$ and $$c\neq 0$$ are integers, then $$a|b$$ if and only if $$ac|bc$$. Exercise 4.35 Prove or disprove with a counterexample. If $$a|m$$ and $$a|(ms+nt)$$ for some integers $$a\neq 0$$, $$m$$, $$s$$, $$n$$, and $$t$$, then $$a|nt$$. Exercise 4.36 Prove that $$7^n-1$$ is divisible by $$6$$ for $$n\geq 1$$. Exercise 4.37 Prove that $$5^n-2^n$$ is divisible by $$3$$ for $$n\geq 1$$. Exercise 4.38 Show that $$f_n\mid f_m$$ when $$n$$ and $$m$$ are positive integers with $$n\mid m$$. Exercise 4.39 Show that the product of every two integers of the form $$6k+1$$ is also of the form $$6k+1.$$ Exercise 4.40 Show that any integer of the form $$6k+5$$ is also of the form $$3 k+2,$$ but not conversely. Exercise 4.41 Given nonzero integers $$a, b,$$ and $$c$$ show that $$a|b$$ and $$a|c$$ implies $$a|(b x+c y)$$ for any integers $$x$$ and $$y.$$ Exercise 4.42 Determine which of the following integers are prime: 201, 207, 213, 203, 211, 221. Exercise 4.43 Find the smallest prime in the arithmetic progression $$a n+b$$. • $$a=3, b=1$$, • $$a=5, b=4$$, • $$a=7, b=12$$, • $$a=11, b=16.$$ Exercise 4.44 Using the sieve of Eratosthenes, find the prime numbers less than 200. Exercise 4.45 Show that $$x^2-x+41$$ is prime for all integers $$x$$ with $$0\leq x\leq 40.$$ Show that it is composite for $$x=41.$$ Exercise 4.46 Show that $$2x^2+11$$ is prime for all integers $$x$$ with $$0\leq x\leq 10.$$ Show that it is composite for $$x=11.$$ Exercise 4.47 Show that $$2x^2+29$$ is prime for all integers $$x$$ with $$0\leq x\leq 28.$$ Show that it is composite for $$x=29.$$ Exercise 4.48 It has been conjectured that there are infinitely many primes of the form $$n^2-2.$$ Exhibit five such examples. Exercise 4.49 Show that any prime of the form $$3n+1$$ is also of the form $$6m+1.$$ Exercise 4.50 Show that each integer of the form $$3n+2$$ has a prime factor of this form. Exercise 4.51 Show the only prime $$p$$ for which $$3p+1$$ is perfect square is $$p=5.$$ Exercise 4.52 Find all primes that are the difference of the fourth powers of two integers. Exercise 4.53 Show that no integer of the form $$n^3+1$$ is a prime, other than $$2.$$ Exercise 4.54 Prove that all odd primes are either of the form $$4n+1$$ or $$4n-1$$ for some $$n\in \mathbb{N}$$. Exercise 4.55 Prove that, if $$n\in \mathbb{N}$$ s a product of primes of the form $$4m+1$$, then $$n$$ must be of that form. Exercise 4.56 Let $$Q_n=p_1p_2\cdot \cdot \cdot p_n+1$$ where $$p_1,p_2,\cdot \cdot \cdot ,p_n$$ are the smallest primes. Determine the smallest prime factor of $$Q_n$$ for $$n=1,2,3,4,5,$$ and 6. Do you think that$ Q_n$is prime infinitely often? Exercise 4.57 Show there are infinitely prime numbers of the form $$4k+3$$. Exercise 4.58 Give an example to show that the following conjecture is not true: Every positive integer can be written in the form $$p+a^2$$, where $$p$$ is either a prime or 1, and $$a\geq 0.$$ Exercise 4.59 Another unproven conjecture is that there are an infinitude of primes that are 1 less than a power of 2, such as $$3=2^2-1.$$ Find four more of these primes. Exercise 4.60 It has been conjectured that every even integer can be written as the difference of consecutive primes in finitely many ways. For example, $$6=29-23=137-131=599-593=1019-1013 = ...$$ Express the integer 10 as the difference of two consecutive primes in 15 ways. Exercise 4.61 Find four primes of the form $$2^n+1$$ for $$n\in \mathbb{N}$$. Exercise 4.62 Prove that if $$2^n+1$$ is prime, then $$n=0$$ or $$n=2k$$ for some integer $$k$$. Exercise 4.63 Prove that $$p$$ is prime if and only if it has no divisors $$d$$ that satisfy $$1<d\leq \sqrt{p}$$. Exercise 4.64 Show there are infinitely many primes of the form $$6k+5.$$ Exercise 4.65 Show that no integer of the form $$n^3+1$$ is a prime, other than $$2.$$ Exercise 4.66 Explain why $$\left(a,a^2\right)=a$$ where $$a$$ is a positive integer. Explain why 201 is not a prime. Explain why 11 is a prime number. Exercise 4.67 Find the greatest common divisor of each of the following pairs of integers. • $$5, 15$$ • 0,100 • $$-27,-45$$ • $$-90, 100$$ • 100, 121 • 1001, 289 Exercise 4.68 Find the greatest common divisor of each of the following. • $$(a,2a)$$ • $$(a,a^2)$$ • $$(a,a+1)$$ • $$(a,a+2)$$ Exercise 4.69 Show that $$(n,1)=1$$ for all integers $$n.$$ Exercise 4.70 Show that $$(n+1,n)=1$$ for all integers $$n.$$ Exercise 4.71 Show that $$(2n+1,2n-1)=1$$ for all integers $$n.$$ Exercise 4.72 Show that if $$a$$ is an even integer and $$b$$ is an odd integer, then $$(a,b)=\left(\frac{a}{2},b\right).$$ Exercise 4.73 Show that if $$a, b,$$ and $$c$$ are integers, then $$[a,b]|c$$ if and only if $$a|c$$ and $$b|c.$$ Exercise 4.74 Show that if $$a$$ and $$b$$ are positive integers, then $$(a,b)=(a+b,[a,b]).$$ Exercise 4.75 Show that $$8a+3$$ and $$5a+2$$ are relatively prime for all integers $$a.$$ Exercise 4.76 For any integer $$a$$ show that $$(2a+1,9a+4)=1.$$ Exercise 4.77 For any integer $$a$$ show that $$(5a+2,7a+3)=1.$$ Exercise 4.78 Show that if $$a$$ is odd, then $$(3a,3a+2)=1.$$ Exercise 4.79 Show that if $$a$$ and $$b$$ are integers with $$(a,b)=1,$$ then $$(a+b,a-b)=1$$ or 2. Exercise 4.80 Show that if $$a$$ and $$b$$ are even integers that are not both zero, then $$(a,b)=2\left(\frac{a}{2},\frac{b}{2}\right).$$ Exercise 4.81 Show that if $$a, b,$$ and $$c$$ are integers such that $$(a,b)=1$$ and $$c|(a+b),$$ then $$(c,a)=(c,b)=1.$$ Exercise 4.82 Show that if $$a, b,$$ and $$c$$ are integers with $$(a,b)=(a,c)=1,$$ then $$(a,b c)=1.$$ Exercise 4.83 Show that if $$a$$ and $$b$$ are relatively prime integers, then $$(a+2b,2a+b)=1$$ or 3. Exercise 4.84 Show that if $$(a,b)=1$$ and $$a|b c$$ then $$a|c.$$ Exercise 4.85 Show that if $$r|a$$, $$r|b$$, and $$r|c$$, then $$r|\gcd(a,b,c)$$. Exercise 4.86 Which of the following are true and which are false? For those that are false provide a counterexample. • If $$a|b$$ and $$b|c$$, then $$a|c$$. • If $$a|c$$ and $$b|d$$, then $$a b |c d$$. • If $$m^2 |n^2$$, then $$m|n$$. • If $$m |n$$, then $$m^2 | n^2$$. • If $$m$$ is a positive integer, then $$\gcd(ma , mb)=m \gcd(a,b)$$. • If $$n |a b$$ and $$n$$$$\not{|} \, \, a$$, then $$n|b$$. • If $$n |a b$$ and $$\gcd(n,a)=1$$, then $$n|b$$. • If $$n$$ is a positive integer, then $$\gcd(a^n,b^n)=\gcd(a,b)^n$$. • If $$n$$ is an integer, then $$\gcd(a,b)=\gcd(a,b+n a)$$. • If $$n$$ is composite and $$n|a b$$, then $$n|a$$ or $$n|b$$. Exercise 4.87 What is $$\left(a^2+b^2,a+b\right),$$ where $$a$$ and $$b$$ are relatively prime integers that are not both 0? ::: {.proof } Let $$p$$ be a prime dividing $$\left(a^2+b^2,a+b\right).$$ Then $p\left|(a+b)^2-\left(a^2+b^2\right)\right.=2 a b.$ Now if $$p|a,$$ then $$p|b$$ since $$p|(a+b).$$ But $$(a,b)=1,$$ so $$p\nmid a.$$ Similarly, $$p\nmid b.$$ Therefore, $$p|2$$ and so $$p=1$$ or $$p=2.$$ If $$a$$ and $$b$$ have the same parity, then $$2|(a+b)$$ and $$2\left|\left(a^2+b^2\right)\right.$$ and so $$\left(a^2+b^2,a+b\right)=2.$$ But if $$a$$ and $$b$$ have opposite parity, then $$a+b$$ and $$\left(a^2+b^2,a+b\right)=1.$$ ::: Exercise 4.88 Show that if $$k$$ is a positive integer, then $$3k+2$$ and $$5k+3$$ are relatively prime. Exercise 4.89 Show that if $$(a,b)=1$$ and $$c|a$$, then $$(c,b)=1$$. Exercise 4.90 Show that if $$a$$, $$b$$, and $$c$$ are integers such that $$(a,b)=1$$ and $$c|(a+b)$$, then $$(c,a)=(c,b)=1$$. Exercise 4.91 Find the greatest common divisor of each of the following pairs of integers. • $$5, 15$$ • 0,100 • $$-27,-45$$ • $$-90, 100$$ • 100, 121 • 1001, 289 Exercise 4.92 What is the greatest common divisor of each of the following? • $$(a,2a)$$ • $$(a,a^2)$$ • $$(a,a+1)$$ • $$(a,a+2)$$ Exercise 4.93 Use the Euclidean Algorithm to find the following greatest common divisors. • $$(221,187)$$ • $$(51,87)$$ • $$(105,300)$$ • $$(34709,100313)$$ • $$(64,38,190)$$ • $$(15,35,90)$$ • $$(100,210,540)$$ • $$(300,2160,5040)$$ • $$(240, 660, 5540, 9980)$$ • $$(1240, 6660, 15540, 19980)$$ Exercise 4.94 Find $$(143,227),$$ $$(306,657),$$ and $$(272,1479).$$ Exercise 4.95 Use the Euclidean Algorithm to find integers $$x$$ and $$y$$ satisfying the following. • $$(56,72)=56x+72y$$ • $$(24,138)=24x+138y$$ • $$(119,272)=119x+272y$$ • $$(1769,2378)=1769x+2378y$$ Exercise 4.96 Find integers $$x$$ and $$y$$ satisfying $(198,288,512)=198x+288y+512z.$ Exercise 4.97 Find $$\gcd (143,227),$$ $$\gcd (306,657),$$ and $$\gcd (272,1479).$$ Exercise 4.98 Show that if $$k>0$$ then $$\gcd (k a,k b)=k \gcd (a,b).$$ Exercise 4.99 Which of the following are true and which are false? For those that are false provide a counterexample. • If $$a|b$$ and $$b|c$$, then $$a|c$$. • If $$a|c$$ and $$b|d$$, then $$a b |c d$$. • If $$m^2 |n^2$$, then $$m|n$$. • If $$m |n$$, then $$m^2 | n^2$$. • If $$m$$ is a positive integer, then $$\gcd(ma , mb)=m \gcd(a,b)$$. • If $$n |a b$$ and $$n$$$$\not{|} \, \, a$$, then $$n|b$$. • If $$n |a b$$ and $$\gcd(n,a)=1$$, then $$n|b$$. • If $$n$$ is a positive integer, then $$\gcd(a^n,b^n)=\gcd(a,b)^n$$. • If $$n$$ is an integer, then $$\gcd(a,b)=\gcd(a,b+n a)$$. • If $$n$$ is composite and $$n|a b$$, then $$n|a$$ or $$n|b$$. Exercise 4.100 Show that if $$r|a$$, $$r|b$$, and $$r|c$$, then $$r|\gcd(a,b,c)$$. Exercise 4.101 Prove that, if $$a_1, a_2,\ldots a_m$$ are pairwise relatively prime, then $(a_1,a_2,\ldots a_n)=1.$ Exercise 4.102 Use the Euclidean algorithm to find $$(1372,490)$$ and write the GCD as a linear combination of 1372 and 490. Exercise 4.103 Use the Euclidean algorithm to find $$d=(500,50,40)$$ and write $$d$$ as a linear combination of the three given integers. Exercise 4.104 Use the Euclidean Algorithm to find $$(28,48,24)$$. Exercise 4.105 Use the Euclidean Algorithm to find $$(28,48,24)$$. Exercise 4.106 Use the Euclidean Algorithm to find $$(34709,100313).$$ Exercise 4.107 Use the Euclidean Algorithm to find the greatest common divisor $$(105,300)$$ and then write this as a linear combination of these integers. Exercise 4.108 Use the Euclidean Algorithm to find the multiplicative inverse for 91 modulo 191. Exercise 4.109 Find the unique prime factorization of $$12446784$$ and of $$2293834752.$$ Exercise 4.110 Factor $$12446784$$ and $$2293834752$$ into a product of primes with the same set of primes with (possibly zero) nonnegative exponents. Exercise 4.111 Find a prime factorization of • $$111111$$, • $$100,000$$, • $$10,500,000$$, and • $$10!$$. Exercise 4.112 Show that all of the prime powers in the prime-power factorization of an integer $$n$$ are even if and only if $$n$$ is a perfect square. Exercise 4.113 Show that if $$a$$ and $$b$$ are positive integers and $$a^3|b^2,$$ then $$a|b.$$ Exercise 4.114 Find the greatest common divisor of each of the following pairs of integers: • $$2^13^25^3$$,$22337^2 $•$2(3)(5)(7), 7(11)(13) $• $$2^83^65^411^{13}$$,$2(3)(5)(11)(13) $• $$41^{101}47^{43}103^{1001}$$, $$41^{11}43^{47}83^{111}$$ Exercise 4.115 Find the least common multiple of each of the following pairs of integers: • $$2^23^35^57^7$$, $$2^73^55^37^2$$ • $$2(3)(5)(7)(11)$$, $$17(19)(23)(29)$$ • $$2^35^711^{13}$$, $$2(3)(5)(7)(11)(13)$$ • $$47^{11}79^{111}101^{1001}$$, $$41^{11}83^{111}101^{1000}$$ Exercise 4.116 Find the least common multiple of each of the following pairs of integers: • $$2^23^35^57^7$$, $$2^73^55^37^2$$ • $$2(3)(5)(7)(11)$$, $$17(19)(23)(29)$$ • $$2^35^711^{13}$$, $$2(3)(5)(7)(11)(13)$$ • $$47^{11}79^{111}101^{1001}$$, $$41^{11}83^{111}101^{1000}$$ Exercise 4.117 If $$p$$ is a prime and $$a$$ is an integer with $$p\left|a^2\right.$$ then $$p|a.$$ Exercise 4.118 Show that if $$a,$$ $$b,$$ and $$c$$ are integers with $$c|a b$$ then $$c|(a,c)(b,c).$$ Exercise 4.119 Find the prime factorization of • $$33,776,925$$ • $$210,733,237$$ • $$1,359,170,111$$ • $$33,108,075$$ • $$7,300,977,607$$ • $$4,165,073,376,607$$. Exercise 4.120 Show that any number of the form $$2^{4 n+2}+1$$ can be factored easily and then show how to factor $$2^{18}+1.$$ Exercise 4.121 Find the unique prime factorization of $$12446784$$ and of $$2293834752.$$ Factor $$12446784$$ and $$2293834752$$ into a product of primes with the same set of primes with (possibly zero) nonnegative exponents. Exercise 4.122 Find a prime factorization of $$111111$$, $$100,000$$, $$10,500,000$$, and $$10!$$. Exercise 4.123 Show that all of the prime powers in the prime-power factorization of an integer $$n$$ are even if and only if $$n$$ is a perfect square. Exercise 4.124 Show that if $$a$$ and $$b$$ are positive integers and $$a^3|b^2,$$ then $$a|b.$$ Exercise 4.125 Show that if $$a,$$ $$b,$$ and $$c$$ are integers with $$c|a b$$ then $$c|(a,c)(b,c).$$ Exercise 4.126 Show that if $$p$$ is prime, $$a$$ is an integer, and $$n$$ is a positive integer such that $$p\left|a^n\right.,$$ then $$p|a.$$ Exercise 4.127 Show that if $$\left.p^a\right\|m$$ and $$\left.p^b\right\|n,$$ then $$\left.p^{a+b}\right\| n m.$$ Exercise 4.128 Show that if $$\left.p^a\right\|m$$ then $$p^{k a}\|m^k$$ for any positive integer $$k.$$ Exercise 4.129 Show that if $$\left.p^a\right\|m$$ and $$\left.p^b\right\|n$$ with $$a\neq b,$$ then $$\left.p^{\min (a,b)}\right\|(m+n).$$ Exercise 4.130 Use the unique factorizations of $$n=5248$$ and $$m=1280$$ to determine the unique factorizations of $$(n,m)$$and $$[n,m].$$ Exercise 4.131 Show that if $$a$$ and $$b$$ are positive integers, then $$(a,b)=(a+b,[a,b]).$$ Exercise 4.132 Write out the unique prime factorization of $$1494411775.$$ Show each step. ## 4.5 Linear Congruence Equations Definition 4.3 Given integers $$a, b$$ and a modulus $$n,$$ a congruence equation of the form $$a x\equiv b \pmod{n}$$ is called a linear congruence where $$x$$ is an unknown. Solvability of a linear congruence $$a x\equiv b \pmod{n}$$ can easily be described by the following: (i) if $$a$$ and $$n$$ are relatively prime then there is precisely one incongruent solution modulo $$n$$, (ii) if the greatest common divisor of $$a$$ and $$n$$ does not divide $$b$$, then the linear congruence has no solution, and (iii) if the gcd of $$a$$ and $$n$$ does divide $$b$$ then there are exactly $$(a,n)$$ distinct incongruent solutions modulo $$n$$. Knowing whether there are solutions to a given linear congruence is often the first step, but as we will see, the work of computing $$(a,n)$$ can be also used in finding solutions, if there are any. Theorem 4.7 Let $$x$$ be an unknown in the linear congruence equation $$a x\equiv b \pmod{n}$$ and $$d=(a,n)$$. • If $$d=1,$$ then there is precisely one solution. • If $$d|b$$ there are exactly $$d$$ distinct solutions, otherwise there are no solutions. Proof. By the Euclidean algorithm there are integers $$s$$ and $$t$$ such that $$a s+n t=1,$$ and then $$a (s b)+n(t b)=b$$ and thus we find that $$x=s b$$ is a solution of the congruence. If $$y$$ is any other solution, then $$a y\equiv b \pmod{n}$$. Thus, $$a x\equiv a y \pmod{n}$$ and since $$(a,n)=1$$ we have $$x\equiv y \pmod{n}$$. Since the congruence is equivalent to $$a x+n(- y)=b$$ in integers $$x$$ and $$y,$$ the existence of solutions $$x$$ and $$y$$ requires that $$d=(a,n)$$ divide $$b$$. Suppose then that this requirement is satisfied and let $$x=x_0+(n/d)t$$ and $$y=y_0+(a/d)t$$ where $$x=x_0$$ and $$y=y_0$$ is a particular solution, be all solutions to $$a x+n(- y)=b$$. Therefore, for any integer $$t,$$ $$x$$ is a solution to $$a x\equiv b \pmod{n}$$. To determine that there are $$d$$ incongruent solutions, we find the condition that describes when two solutions are congruent modulo $$n$$. Suppose we have two solutions, namely, $x_0+\left(\frac{n}{d}\right)t_1\equiv x_0+\left(\frac{n}{d}\right)t_2 \pmod{n}.$ Since $\left(\frac{n}{d},n\right)=\frac{n}{d},$ it follows that $$t_1\equiv t_2 \pmod{d}$$. This show that a complete set of incongruent solutions is obtained by taking $$x=x_0+\left(\frac{n}{d}\right)t$$ and $$t$$ ranges through a complete system of residues modulo $$d;$$ one such set is given by $$t=0,1,2, \ldots ,d-1$$. Example 4.5 Solve the linear congruence $$131 x\equiv 21 \pmod{77}$$. Solution. Because $$1=(131,77)|21$$ there is a unique solution modulo 77. We have $$54x\equiv 21 \pmod{77}$$ and dividing by $$3$$ we have $$18 x\equiv 7 \pmod{77}$$. Next multiplying by $$4$$ we have $$72 x\equiv 28 \pmod{77}$$ and so $$-5x\equiv 28\equiv 105 \pmod{77}$$. Therefore, $$x\equiv -21\equiv 56 \pmod{77}$$. Example 4.6 Solve the linear congruence $$6x\equiv (10)^k \pmod{21}$$. Solution. There is no solution because $$(6,21)=3$$ does not divide $$2^k5^k$$ for any positive integer $$k$$. Example 4.7 Solve the linear congruence $$91 x\equiv 98 \pmod{119}$$. Solution. Because $$7=(91,119)|98$$ there are $$7$$ incongruent solutions modulo $$119$$. We use cancellation to simplify the congruence to $$13 x\equiv 14 \pmod{17}$$. We have $$-4x\equiv -3\equiv -20 \pmod{17}$$. Therefore, in terms of the original modulus, the solutions are $x\equiv 5, 22, 39, 56, 73, 90, 107 \pmod{199}. \square$ Example 4.8 Solve the linear congruence $$31 x\equiv 12 \pmod{24}$$. Solution. Since $$(31,24)=1$$ and $$1|12$$ there is exactly one incongruent solution modulo $$24$$. To find this solution we use $$31\equiv 7 \pmod{24}$$ so $$31 x\equiv 7x \pmod{24}$$ which means we now solve the linear congruence $$7x\equiv 12 \pmod{24}$$. Next we multiply by 7, to obtain $$49x\equiv 84 \pmod{24}$$. Then since $$49\equiv 1 \pmod{24}$$ and $$84\equiv 12 \pmod{24}$$ we now have $$x\equiv 12 \pmod{24}$$ as our solution to the linear congruence $$31 x\equiv 12 \pmod{24}$$. Example 4.9 Solve the linear congruence $$987 x\equiv 610 \pmod{1597}$$. Solution. Solving the linear congruence equation is equivalent to solving the linear Diophantine equation $$987 x+1597 (-y)=610$$ for $$x$$ and $$y$$. There is a solution because $$(987,1597)=1$$ and it is unique modulo $$1597$$. A particular solution is $$x=-1$$ and $$y=-1$$. Thus all solutions to the Diophantine equations are $x=-1+\frac{1597}{1}t \quad \text{ and } \quad y=-1+\frac{987}{1}t.$ Suppose that $-1+\frac{1597}{1}t_1\equiv -1+\frac{1597}{1}t_2 \pmod{1597}$ are two solutions to the congruence equation. Then clearly, $$t_1\equiv t_2 \pmod{1597}$$. This show that a complete set of incongruent solutions is obtained by taking $$x=-1+1597t$$ and $$t=0$$. Therefore, the unique solution is $$x\equiv 1596 \pmod{1597}$$. Example 4.10 Solve the linear congruence $$42 x\equiv 50 \pmod{76}$$. Solution. Solving the linear congruence equation is equivalent to solving the linear Diophantine equation $$42 x+76(- y)=50$$ for $$x$$ and $$y$$. There is a solution because $$(42,76)=2$$ and $$2|50;$$ and so there are exactly two solutions modulo $$76$$. A particular solution is $$x=-35$$ and $$y=20$$. Thus all solutions for $$42 x+76(- y)=50$$ are $x=-35+\frac{76}{2}t \qquad \text{and} \qquad y=20+\frac{42}{2}t.$ Suppose that $$-35+38t_1\equiv -35+38t_2\pmod{76}$$ are two solutions. Since $$(38,76)=38,$$ we have, $$t_1\equiv t_2 \pmod{2}$$. This show that a complete set of incongruent solutions is obtained by taking $$x=-35+38t$$ and $$t=0,1,2, \ldots ,d-1$$ where $$d=(42,76)=2$$. Therefore, the solutions are $$x\equiv 3 \pmod{76}$$ and $$x\equiv 41 \pmod{76}$$. Notice that to solve a linear congruence equation $$a x\equiv b \pmod{n}$$ we find, (if possible) an integer $$h$$ such that $$a h\equiv 1 \pmod{n}$$ and then using $$h$$ we solve by multiplying by $$h$$, obtaining $$x\equiv h b \pmod{n}$$. Definition 4.4 Let $$a$$ be an integer with $$(a,n)=1$$. Then a solution of the linear congruence $$a x\equiv 1 \pmod{n}$$ is called an inverse of $$a$$. Theorem 4.8 Let $$p$$ be a prime. The positive integer $$a$$ is its own inverse modulo $$p$$ if and only if $$a\equiv 1 \pmod{p}$$ or $$a\equiv -1 \pmod{p}$$. Proof. If $$a$$ is its own inverse modulo $$p,$$ then $$a^2\equiv 1 \pmod{p}$$. Thus, $$p\left|\left(a^2-1\right)\right.$$ and so either $$p|(a-1)$$ or $$p|(a+1)$$. Therefore, $$a\equiv 1 \pmod{p}$$ or $$a\equiv -1 \pmod{p}$$. Conversely, if $$a\equiv 1 \pmod{p}$$ or $$a\equiv -1 \pmod{p},$$ then $$a^2\equiv 1 \pmod{p},$$ so that $$a$$ is its own inverse modulo $$p$$. Example 4.11 By finding an inverse, solve the linear congruence $$37x\equiv b \pmod{53}$$. Solution. First we solve, $$37 x\equiv 1 \pmod{53}$$. We have $$-16x\equiv 1\equiv 54 \pmod{53}$$. Now dividing by $$2$$ and simplifying, we have $$8x\equiv -27\equiv 26\equiv 132 \pmod{53}$$ Again dividing by $$2$$ and simplifying, we have $$2x\equiv 33\equiv 86 \pmod{53}$$ Therefore, $$x\equiv 43 \pmod{53}$$. Now to solve $$37 x\equiv b \pmod{53}$$ we multiply by $$43$$ and we have $$(43) 37 x\equiv 43 b \pmod{53}$$. Thus $$x\equiv 43 b \pmod{53}$$ is the solution. Example 4.12 By finding an inverse, solve the linear congruence $$31 x\equiv 12 \pmod{24}$$. Solution. Recall that since $$(31,24)=1$$ and $$1|12$$ there is exactly one incongruent solution modulo $$24$$. To find this solution let’s use the definition of congruence, namely $$24|(31x-12)$$ which means there exists an integer $$y$$ such that $$31x-12=24y$$ and so we will solve the linear Diophantine equation $$31x+24(-y)=12$$. Now notice that we merely need the $$x$$ solutions because of our original linear congruence involves only $$x$$. But first we need a particular solution to this linear Diophantine equation, which can be found using the Euclidean algorithm, $$31=1(24)+7$$ with $$0\leq 7<24$$ $$24=3(7)+3,$$ with $$0\leq 2<7$$ $$7=2(3)+1$$, with $$0\leq 1<2$$ so $$(31,24)=1$$ which we already knew but now we can use back substitution to find 1 as a linear combination of $$31$$ and $$24,$$ namely, $$1=7-2(3)$$, $$1=7-2(24-3(7))$$, $$1=(7)7+(-2)(24)$$, $$1=(7)(31-1(24))+(-2)(24)$$, $$1=(7)(31)+(-9)(24)$$. Then multiplying by 12 yields a particular solution with $$x_0=84$$ since, $$12=(31)(84)+(24)(-108)$$, So all solutions to the linear Diophantine equation $$31x+24(-y)=12$$ are given $$x=84+24t$$ where $$t\in \mathbb{Z}$$. In particular when $$t=-3$$ we find the solution $$x\equiv 12 \pmod{24}$$. Example 4.13 By finding an inverse, solve the linear congruence $$78 x\equiv 12 \pmod{240}$$. Solution. Since $$(78,240)=6$$ and $$6|12$$ there are exactly six incongruent solution modulo $$240$$. To find these solutions let’s use the definition of congruence, namely $$240|(78x-12)$$ which means there exists an integer $$y$$ such that $$78x-12=240y$$ and so we will solve the linear Diophantine equation $$78x+240(-y)=12$$. Using the Euclidean algorithm, $$240=3(78)+6, \text{with} 0\leq 7<24$$ and now we can write 6 as a linear combination of $$78$$ and $$240,$$ namely, $$6=(-3)(78)+(1)(240)$$ Then multiplying by 2 yields a particular solution with $$x_0=-6$$ since, $$12=(-6)(78)+(2)(240)$$, So all solutions to the linear Diophantine equation $$78x-12=240y$$ are given $$x=-6+\frac{240}{6}t=-6+40t$$ where $$t\in \mathbb{Z}$$. In particular, when $$t=1,2,3,4,5,6,7$$ we find the six incongruent solutions modulo 240, $$x\equiv 34,74,114,154,194 ,234 \pmod{240}$$. Example 4.14 For which integers $$c,$$ $$0\leq c\leq 1001,$$ does the congruence $$154x\equiv c \pmod{1001}$$ have solutions? When there are solutions, how many incongruent solutions are there? ## 4.6 Chinese Remainder Theorem The Chinese Remainder Theorem is a staple in many high-level mathematics courses. This theorem has been used for centuries to help mathematicians solve complex problems, and it’s an essential tool for anyone looking to pursue a career in mathematics. In this Definitive Guide, you’ll learn everything you need to know about the Chinese Remainder Theorem, from its history to its many applications. The Chinese Remainder Theorem is a mathematical theorem that states that if there are a certain number of integers that are all coprime to each other, then for any integer N that is congruent to each modulo ni, there is exactly one such congruence class modulo M. In other words, the Chinese Remainder Theorem allows you to solve a system of linear congruence equations with a unique solution. The Chinese Remainder Theorem is an important tool in number theory and has a wide range of applications, including cryptography and computer science. The Chinese Remainder Theorem is a mathematical theorem with a wide range of applications. In its simplest form, the theorem states that if one knows the remainders of a number when it is divided by a set of co-prime numbers, then one can determine the number itself. The theorem has a wide range of applications, from helping to solve simple arithmetic problems to more complex applications in cryptography and computer science. For example, the Chinese Remainder Theorem can be used to find the last digit of a very large number, something that is often useful in mathematical contests. It can also be used to design algorithms for factoring large numbers, a critical task in cryptography. Chinese Remainder Theorem is a mathematics theorem that helps one to find the value of a certain number when its value is unknown. It was developed by Chinese mathematician Sun Zi during the 3rd century BC, and it has since been used by mathematicians and scientists all over the world. Chinese Remainder Theorem is a powerful tool that can be used to solve a variety of mathematical problems. However, it is not without its challenges. One of the biggest challenges is that it can be difficult to find the values of x that satisfy all the congruences. This can be particularly tricky when there are a large number of congruences. Additionally, the Chinese Remainder Theorem can only be used when the moduli are relatively prime. This can sometimes be difficult to determine, especially when working with larger numbers. Despite these challenges, the Chinese Remainder Theorem remains a valuable tool for mathematicians and can be used to solve a variety of problems. The theorem has been used in a variety of applications, ranging from number theory to cryptography. However, the Chinese Remainder Theorem was not always so well-known. In fact, it was not until the 19th century that the theorem began to be widely used. This is largely due to the work of Chinese mathematician Sun Tzu, who provided the first complete proof of the theorem. Since then, the Chinese Remainder Theorem has been studied by mathematicians all over the world and has become an essential tool in many different fields. The Chinese Remainder Theorem has a wide range of applications, from cryptography to music composition. In cryptography, the theorem is used to design schemes for secret sharing and public-key encryption. In music composition, it can be used to create patterns that are both complex and pleasing to the ear. The theorem can also be used to solve certain number theory problems, such as finding the order of an element in a finite group. In addition, the Chinese Remainder Theorem has applications in computer science, particularly in the area of error-correcting codes. Overall, the Chinese Remainder Theorem is a powerful tool with a wide range of applications. Today, the theorem is still an active area of research, with new applications being discovered regularly. As such, it is clear that the Chinese Remainder Theorem has had a significant impact on Mathematics and its development. This book is written for people who want to learn about the Chinese Remainder Theorem. It will cover the basics of the theorem, as well as some more advanced topics. I’ll also share my own experience teaching this theorem to students. One of the most essential subjects in mathematics is number theory. This branch of mathematics deals with the properties and relationships between integers, which are the building blocks of all other numbers. It is a critical tool for solving problems in other areas of mathematics, as well as in physics and engineering. Despite its importance, number theory can be challenging for students to grasp. In this book, we will cover the fundamental concepts of the Chinese Remainder Theorem, and provide tips on how to make the material engaging and relevant. The Chinese Remainder Theorem is a staple in many high-level mathematics courses for good reason. This theorem has been used for centuries to help mathematicians solve complex problems, and it’s an essential tool for anyone looking to pursue a career in mathematics. In this Definitive Guide, you’ll learn everything you need to know about the Chinese Remainder Theorem, from its history to its many applications. If you’re looking for a comprehensive guide to the Chinese Remainder Theorem, then look no further than this book. ## 4.7 Chinese Remainder Theorem When solving a linear congruence with a large modulus it is sometimes useful to reduce the linear congruence to a system of linear congruences with smaller moduli. Being able to construct a solution to the original congruence from a linear system of congruence equations is where the Chinese Remainder Theorem is often applied. The Chinese Remainder Theorem is also useful of resolving elementary word problems, as such some are given in the exercises at the end of the section. Now to see how the Chinese Remainder Theorem works it’s useful to see an example first. Let’s solve the following linear system of congruence equations. $$$\label{crtex} \begin{cases} x\equiv 15 \pmod{27} \\ x\equiv 16 \pmod{20} \end{cases}$$$ Notice, $$20$$ and $$27$$ are relatively prime, so we can find integers $$a$$ and $$b$$ such that $$20a+27b=1$$. In fact by inspection, we find $$a=-4$$ and $$b=3$$ since $$20(-4)+27(3)=1$$. We claim $$x=15(20)(-4)+16(27)(3)=96$$ is a solution to both linear congruence equations in $$\ref{crtex}$$. More specifically, we will say, $$x\equiv 96 \pmod{540}$$ is solution to the system in $$\ref{crtex}$$ where $$540=(20)(27)$$. This strategy and the uniqueness is justified in the following well-known theorem. Example 4.15 Solve the linear system of congruences $\begin{cases} x\equiv 2 \pmod{3} \\ x\equiv 5 \pmod{4} \\ x\equiv -3 \pmod{7} \end{cases}$ Solution. We find $$N=(3)(4)(7)=84$$ and we use a table to construct the solution. $\begin{array}{c|c|c|c|c} i & n_i & a_i & \bar{n}_i & u_i \\ \hline 1 & 3 & 2 & 84/3=28 & 28u_1\equiv 1 \pmod{3} \Longrightarrow u_1=1 \\ 2 & 4 & 5 & 84/4=21 & 21u_2\equiv 1 \pmod{4} \Longrightarrow u_2=1 \\ 3 & 7 & -3 & 84/7=12 & 12u_3\equiv 1 \pmod{7} \Longrightarrow u_3=3 \end{array}$ By $$\ref{Chinese Remainder I}$$ the solution to the system is $$$\label{solone} x=(2)(28)(1)+(5)(21)(1)+(-3)(12)(3)=53 \pmod{84}.$$$ as wanted. Theorem 4.9 [Chinese Remainder I] Suppose $$n_1,$$ $$n_2,$$ …, $$n_s$$ are pairwise relatively prime positive integers. Then the system of congruences $$$\label{thm:cr2} \begin{cases} x\equiv a_1 \pmod{n_1} \\ x\equiv a_2 \pmod{n_2} \\ \quad \vdots \\ x\equiv a_s \pmod{n_s} \\ \end{cases} \tag{*}$$$ has a unique solution modulo $$N=n_1n_2\cdot \cdot \cdot n_s.$$ Proof. Let $$\bar{n}_i=N\left/n_i.\right.$$ We know that $$\left(n_i,\bar{n}_i\right)=1$$ for $$i=1, ... ,s$$ because $$\left(n_i,n_j\right)=1$$ whenever $$i\neq j.$$ Therefore, for each $$i,$$ there are integers $$v_i$$ and $$u_i$$ such that $$v_i n_i+u_i \bar{n}_i=1;$$ and using these $$u_i$$ we can construct a solution to the system as $x=a_1\bar{n}_1u_1+a_2\bar{n}_2u_2+\cdots+a_s\bar{n}_su_s.$ To verify this is a solution, check the $$i^{\text{th}}$$ congruence equation in $$\ref{thm:cr2}$$, namely, $x=\sum _{k=1}^s a_k\bar{n}_ku_k\equiv a_i\bar{n}_iu_i\equiv a_i \pmod{n_i}$ for $$1\leq i\leq s$$. To prove uniqueness, assume $$y$$ is a solution to the system of congruences. Then $$x_0\equiv a_i\equiv y \pmod{n_i}$$ for $$1\leq i\leq s$$. Hence, $$n_i|\left(x_0-y\right)$$ for each $$n_i$$ and since no two of the $$n_i$$ have a common factor, $$n_1n_2\cdot \cdot \cdot n_s|\left(x_0-y\right),$$ that is $$N\left|\left(x_0-y\right).\right.$$ Thus, $$y\equiv x_0 \pmod{N}.$$ Example 4.16 Solve the linear system of congruences. $\begin{cases} x\equiv 3 \pmod{5} \\ x\equiv 2 \pmod{6} \\ x\equiv 4 \pmod{7}. \end{cases}$ Solution. We find $$N=(5)(6)(7)=210$$ and we use a table to construct the solution. $\begin{array}{c|c|c|c|c} i & n_i & a_i & \bar{n}_i & u_i \\ \hline 1 & 5 & 3 & 210/5=42 & 42u_1\equiv 1 \pmod{5} \Longrightarrow u_1=3 \\ 2 & 6 & 2 & 210/6=35 & 35u_2\equiv 1 \pmod{6} \Longrightarrow u_2=5 \\ 3 & 7 & 4 & 210/7=30 & 30u_3\equiv 1 \pmod{7} \Longrightarrow u_3=4 \end{array}$ By $$\ref{Chinese Remainder I}$$ the solution is $x=(3)(42)(3)+(2)(35)(5)+(4)(30)(4)=1208\equiv 158 \pmod{210}.$ as desired. Example 4.17 Solve the linear system of congruences. $\begin{cases} x\equiv 2 \pmod{3} \\ x\equiv 3 \pmod{5} \\ x\equiv 2 \pmod{7}. \end{cases}$ Solution. We find $$N=(3)(5)(7)=105$$ and we use a table to construct the solution. $\begin{array}{c|c|c|c|c} i & n_i & a_i & \bar{n}_i & u_i \\ \hline 1 & 3 & 2 & 105/3=35 & 35u_1\equiv 1 \pmod{3} \Longrightarrow u_1=2 \\ 2 & 5 & 3 & 105/5=21 & 21u_2\equiv 1 \pmod{5} \Longrightarrow u_2=1 \\ 3 & 7 & 2 & 105/7=15 & 15u_3\equiv 1 \pmod{7} \Longrightarrow u_3=1 \end{array}$ Therefore, $x_0=(2)(35)(2)+(3)(21)(1)+(2)(15)(1)=263\equiv 23 \pmod{105}.$ is the solution by the $$\ref{Chinese Remainder I}$$. Example 4.18 Solve the linear system of congruences. $\begin{cases} x\equiv 1 \pmod{2} \\ x\equiv 2 \pmod{3} \\ x\equiv 3 \pmod{5} \\ x\equiv 4 \pmod{7}. \end{cases}$ Solution. We find $$N=(2)(3)(5)(7)=210$$ and we use a table to construct the solution. $\begin{array}{c|c|c|c|c} i & n_i & a_i & \bar{n}_i & u_i \\ \hline 1 & 2 & 1 & 210/2=105 & 105u_1\equiv 1 \pmod{2} \Longrightarrow u_1=1 \\ 2 & 3 & 2 & 210/3=70 & 70u_2\equiv 1 \pmod{3} \Longrightarrow u_2=1 \\ 3 & 5 & 3 & 210/5=42 & 42u_3\equiv 1 \pmod{5} \Longrightarrow u_3=3 \\ 4 & 7 & 4 & 210/7=30 & 30u_4\equiv 1 \pmod{7} \Longrightarrow u_3=4 \end{array}$ By $$\ref{Chinese Remainder I}$$ the solution is $x_0=(1)(105)(1)+(2)(70)(1)+(3)(42)(3)+(4)(30)(4)=1103\equiv 53 \pmod{210}.$ as desired. Theorem 4.10 [Chinese Remainder Theorem II] Suppose $$n_1, n_2,, \ldots n_s$$ are pairwise relatively prime positive integers and that $$\left(a_i,n_i\right)=1$$ for each $$i.$$ Then the system of congruences $$a_1 x\equiv b_1 \pmod{n_1}$$, $$a_2 x\equiv b_2 \pmod{n_2}$$, $$\ldots$$, $$a_s x\equiv b_s \pmod{n_s}$$ has a unique solution modulo $$N=n_1n_2\cdot \cdot \cdot n_s.$$ Solution. Since $$\left(a_i,n_i\right)=1$$ for each $$i,$$ we know that each congruence in the system has a solution, we first choose integers $$x_1, x_2, ... ,x_s$$ such that $$a_i x_i\equiv b_i \pmod{n_i}.$$ Let $$\bar{n}_i=N\left/n_i\right.$$ and since no two of the $$n_i$$ have a common factor, we see that $$\left(n_i,\bar{n}_i\right)=1.$$ Thus there is integer $$u_i$$ such that $$\bar{n}_iu_i\equiv 1 \pmod{n_i}.$$ We now show that the number $$x_0$$ defined by $x_0=\sum _{i=1}^s x_i\bar{n}_iu_i$ is a solution of the original system of congruences. First note that $$n_i$$ divides each $$\bar{n}_i$$ when $$j\neq i.$$ Thus for each $$i,$$ we have, $a_ix_0=\sum _{k=1}^s a_k x_k \overline{n}_k u_k\equiv a_ix_i\equiv b \pmod{n_i}.$ Hence, $$x_0$$ is s solution of each congruence. If $$y$$ is a solution to the system of congruences, then $$x_0\equiv x_i\equiv y \pmod{n_i}.$$ Hence, $$n_i|\left(x_0-y\right)$$ for each $$n_i$$ and since no two of the $$n_i$$ have a common factor, $$n_1n_2\cdot \cdot \cdot n_s|\left(x_0-y\right),$$ that is $$N\left|\left(x_0-y\right).\right.$$ Thus, $$y\equiv x_0 \pmod{N}.$$ Example 4.19 Solve the linear system of congruences. $\begin{cases} 2 x\equiv 3 \pmod{7} \\ 3x\equiv 4 \pmod{5} \\ 5 x\equiv 46 \pmod{51} \end{cases}$ Solution. We find $$N=(7)(5)(51)=1785$$ and we use a table to construct the solution. $\begin{array}{c|c|c|c|c|c|c} i & n_i & a_i & b_i & a_i x_i \equiv b_i \pmod{n_i} & \bar{n}_i & \bar{n}_iu_i \equiv 1 \pmod{n_i} \\ \hline 1 & 7 & 2 & 3 & x_1=5 & 255 & u_1=5 \\ 2 & 5 & 3 & 4 & x_2=3 & 357 & u_2=3 \\ 3 & 51 & 5 & 46 & x_3=50 & 35 & u_3=35 \end{array}$ By $$\ref{Chinese Remainder II}$$ the solution is $x_0=(5)(255)(5)+(3)(357)(3)+(50)(35)(35)=70838 \equiv 1223 \pmod{1785}.$ as required. ## 4.8 Exercises Exercise 4.133 Show that each of the following congruences hold. • $$13\equiv 1 \pmod{2}$$ • $$-2\equiv 1 \pmod{3}$$ • $$22\equiv 7 \pmod{5}$$ • $$-3\equiv 30 \pmod{11}$$ • $$91\equiv 0 \pmod{13}$$ • $$111\equiv -9 \pmod{40}$$ • $$69\equiv 62 \pmod{7}$$ • $$666\equiv 0 \pmod{37}$$ • $$166\equiv 13 \pmod{17}$$ Exercise 4.134 Determine whether each of the following pairs of integers is congruent modulo 7. •$1,15 $•$-1,8 $•$0,42 $•$-9,5 $•$2,99 \$
• $$-1,699$$

Exercise 4.135 Show that if $$a$$ is an even integer, then $$a^2\equiv 0 \pmod{4},$$ and if $$a$$ is an odd integer then $$a^2\equiv 1 \pmod{4}.$$

Exercise 4.136 Show that if $$a$$ is an odd integer, then $$a^2\equiv 1 \pmod{8}.$$

Exercise 4.137 Show that if $$a, b, m,$$ and $$n$$ are integers such that $$m>0,$$ $$n>0,$$ $$n|m,$$ and $$a\equiv b \pmod{m},$$ then $$a\equiv b \pmod{n}.$$

Exercise 4.138 Show that if $$a, b, c,$$ and $$m$$ are integers such that $$c>0,$$ $$m>0,$$ and $$a\equiv b \pmod{m},$$ then $$a c\equiv b c \pmod{m c}.$$

Exercise 4.139 Show that if $$a, b,$$ and $$c$$ are integers such that $$c>0,$$ such that $$a\equiv b \pmod{c},$$ then $$(a,c)=(b,c).$$

Exercise 4.140 Find the least nonnegative residue modulo 13 of each of the following integers:

• $$22$$
• $$-1$$
• $$100$$
• $$-100$$
• $$1001$$
• $$-1000$$

Exercise 4.141 Find the least positive residue of $$1!+2!+3!+\cdots +100!$$ modulo each of the following integers.

• 2
• 12
• 7
• 25

Exercise 4.142 Find the least residue of $$a$$ modulo $$n.$$

• $$a=1348, n=45$$
• $$a=341123, n=234$$
• $$a=809834, n=112$$
• $$a=20934, n=29$$
• $$a=20034, n=23$$
• $$a=3407, n=128$$
• $$a=29976, n=134$$
• $$a=34534, n=93$$
• $$a=345996, n=238$$
• $$a=88629, n=34$$
• $$a=929001, n=222$$
• $$a=987559, n=367$$

Exercise 4.143 Construct tables for addition modulo 8, subtraction modulo 8, and multiplication modulo 8.

Exercise 4.144 What can you conclude if $$a^2\equiv b^2 \pmod{p},$$ where $$a$$ and $$b$$ are integers and $$p$$ is prime?

Exercise 4.145 Show that if $$n$$ is odd positive integer, then $$1+2+3+\cdots +(n-1)\equiv 0 \pmod{n}.$$

Exercise 4.146 Show by mathematical induction that if $$n$$ is a positive integer, then $$4^n\equiv 1+3n \pmod{9}.$$

Exercise 4.147 Show by mathematical induction that if $$n$$ is a positive integer, then $$5^n\equiv 1+4n \pmod{16}.$$

Exercise 4.148 Determine which of the following are true:
- $$7\equiv -34 \pmod{9}$$ - $$-50\equiv 2 \pmod{13}$$ - $$17\equiv 62 \pmod{90}$$
- $$-73\equiv -29 \pmod{128}$$

Exercise 4.149 Find the least residue of $$b$$ modulo $$m$$ given:

• $$m=41,522;$$ $$b=-16,115$$
• $$m=91,631;$$ $$b=-2152$$
• $$m=63;$$ $$b=752\cdot 571$$
• $$m=51;$$ $$b=414\cdot 566$$

Exercise 4.150 What is the least residue of $$100^6$$ modulo $$49?$$ What is the least residue of $$49^4$$ modulo $$23?$$

Exercise 4.151 Show that the following statements are true or determine if they are false by providing a counterexample.

• If $$a\equiv b \pmod{n}$$ and $$m|n$$ then $$a\equiv b \pmod{m}.$$
• If $$a\equiv b \pmod{n}$$ and $$c>0,$$ then $$c a\equiv c b \pmod{c n}.$$
• If $$a\equiv b \pmod{n}$$ and the integers $$a, b,n$$ are divisible by $$d>0,$$ then $$a/d\equiv b/d \pmod{n/d}.$$
• If $$a^2\equiv b^2 \pmod{n}$$ then $$a\equiv b \pmod{n}.$$
• If $$a\equiv b \pmod{n}$$ then $$(a,n)=(b,n).$$

Exercise 4.152 Show that $$53^{103}+103^{53}$$ is divisible by $$39$$.

Exercise 4.153 Show that $$111^{333}+333^{111}$$ is divisible by $$7$$.

Exercise 4.154 Show by mathematical induction that if $$n$$ is a positive integer, then $$5^n\equiv 1+4n \pmod{16}$$.

Exercise 4.155 What can you conclude if $$a^2\equiv b^2 \pmod{p}$$, where $$a$$ and $$b$$ are integers and $$p$$ is prime?

Exercise 4.156 Show that if $$n$$ is an odd positive integer, then $$1+2+3+\cdots +(n-1)\equiv 0 \pmod{n}.$$ Is this statement true if $$n$$ is even?

Exercise 4.157 Show that if $$n$$ is an odd integer or if $$n$$ is a positive integer divisible by $$4$$, then $$1^3+2^3+3^3+\cdots +(n-1)^3\equiv 0 \pmod{n}.$$ Is this statement true if $$n$$ is not divisible by $$4$$?

Exercise 4.158 For which positive integers $$n$$ is it true that $$1^2+2^2+3^2+\cdots +(n-1)^2\equiv 0 \pmod{n}.$$

Exercise 4.159 Construct the multiplication and addition tables for modular arithmetic for $$n=6.$$

Exercise 4.160 Prove that if $$a\equiv b (\text{mod} m)$$ then $$a^k\equiv b^k (\text{mod} m)$$ for every positive integer $$k.$$

Exercise 4.161 For which integers $$c,$$ $$0\leq c\leq 1001,$$ does the congruence $$154x\equiv c \pmod{1001}$$ have solutions? When there are solutions, how many incongruent solutions are there?

Exercise 4.162 Solve the linear congruence equation $$a x\equiv b \pmod{n}$$.

• $$a=1348,b=123, n=45$$
• $$a=341123, b=325, n=234$$
• $$a=809834,b=239, n=112$$
• $$a=20934,b=198, n=29$$
• $$a=20034,b=314, n=23$$
• $$a=3407,b=349, n=128$$
• $$a=29976,b=276, n=134$$
• $$a=34534,b=39, n=93$$
• $$a=345996,b=967, n=238$$
• $$a=88629,b=865, n=34$$
• $$a=929001,b=229, n=222$$
• $$a=987559,b=143, n=367$$

Exercise 4.163 Determine which integers $$a,$$ where $$1\leq a\leq 14,$$ have an inverse modulo 14 and for each one find its inverse.

Exercise 4.164 Determine which integers $$a,$$ where $$1\leq a\leq 30,$$ have an inverse modulo 30 and for each one find its inverse.

Exercise 4.165 Show that if $$\bar{a}$$ is an inverse of $$a$$ modulo $$m$$ and $$\bar{b}$$ is an inverse of $$b$$ modulo $$m,$$ then $$\bar{a} \bar{b}$$ is an inverse of $$a b$$ modulo $$m.$$

Exercise 4.166 Find all solutions to the following linear congruence equations.

• $$3x\equiv 2 \pmod{7}$$
• $$6x\equiv 3 \pmod{9}$$
• $$17x\equiv 14 \pmod{21}$$
• $$15x\equiv 9 \pmod{25}$$
• $$128x\equiv 833 \pmod{1001}$$
• $$987x\equiv 610 \pmod{1597}$$
• $$36x\equiv 30 \pmod{42}$$
• $$143x\equiv 169 \pmod{110}$$
• $$51 x\equiv 0 \pmod{17}$$
• $$52 x\equiv 0 \pmod{17}$$
• $$253 x\equiv 341 \pmod{299}$$
• $$441 x\equiv 465 \pmod{640}$$
• $$36x\equiv 8 \pmod{102}$$
• $$34x\equiv 60 \pmod{98}$$
• $$140 x\equiv 133 \pmod{30}$$
• $$140 x\equiv 133 \pmod{31}$$

Exercise 4.167 Find all solutions of the linear congruence $3x-7y\equiv 11 \pmod{13}.$

Exercise 4.168 What can you conclude if $$a^2\equiv b^2 \pmod{p}$$, where $$a$$ and $$b$$ are integers and $$p$$ is prime?

Exercise 4.169 Show that if $$n$$ is an odd positive integer, then $1+2+3+\cdots +(n-1)\equiv 0 \pmod{n}.$ Is this statement true of $$n$$ is even?

Exercise 4.170 Show that if $$n$$ is an odd integer or if $$n$$ is a positive integer divisible by $$4$$, then $1^3+2^3+3^3+\cdots +(n-1)^3\equiv 0 \pmod{n}.$ Is this statement true if $$n$$ is not divisible by $$4$$?

Exercise 4.171 For which positive integers $$n$$ is it true that $1^2+2^2+3^2+\cdots +(n-1)^2\equiv 0 \pmod{n}.$

Exercise 4.172 Show by mathematical induction that if $$n$$ is a positive integer, then $$5^n\equiv 1+4n \pmod{16}$$.

Exercise 4.173 Give a complete system of residues modulo 13 consisting of entirely odd integers.

Exercise 4.174 An astronomer knows that a satellite orbits the Earth in a period that is an exact multiple of 1 hour that is less than 1 day. If the astronomer notes that the satellite completes 11 orbits in an interval that starts when a 24-hour clock reads 0 hours and ends when the clock reads 17 hours, how long is the orbital period of the satellite?

Exercise 4.175 Solve the linear congruence equation $$987x\equiv 610 (\text{mod} 1597).$$

Exercise 4.176 Solve the linear congruence equation $$987x\equiv 610 (\text{mod} 1597).$$ If you find solutions explain why you have found them all.

Exercise 4.177 Suppose $$p\equiv 3 \pmod{4}$$. Show that $$(p+1)/4$$ is an integer and is the multiplicative inverse of 4 modulo $$p$$.

Exercise 4.178 Explain why the linear congruence equation $$3x\equiv 81 (\text{mod} 910)$$ is solvable or not solvable. If possible solve it.

Exercise 4.179 Find an integer that leaves remainder of 1 when divided by either 2 or 5, but that is divisible by 3.

Exercise 4.180 Find an integer that leaves remainder of 9 when it is divided by either 10 or 11, but that is divisible by 13.

Exercise 4.181 A certain integer between $$1$$ and $$1200$$ leaves the remainder $$1, 2, 6$$ when divided by $$9, 11, 13$$ respectively. What is the integer?

Exercise 4.182 For which integers $$c$$, does $$12x\equiv c \pmod{30}$$ have solutions? When there are solutions are many are there?

Exercise 4.183 Determine which integers $$a$$ have inverse modulo $$14$$ and then find each of the inverses.

Exercise 4.184 Find all solutions to the linear congruence equations $$6x+3y\equiv 12 \pmod{13}$$ and $$10x+5y\equiv 9 \pmod{15}$$.

Exercise 4.185 A professor feeds his pet python every fours days and bathes it once a week. This week he fed it on Tuesday and washed it on Wednesday. When if ever, will he feed and wash the Python on the same day? How often will this happen?

Exercise 4.186 A professor buys a new car every three years; he bought his first in 1981. He gets a sabbatical leave every seven years, starting in 1992. When will he first get both during a leap year?

Exercise 4.187 On the Fourth of July, a professor took a red pill at 8 a.m. and a green pill at noon. The next day he took a white pill at 10 p.m. He takes the red, green, and white pill every 5, 7, and 24 hours, respectively. How often does he take all three together? When in August will this first happen, if at all?

Exercise 4.188 Solve the linear system of congruences.
$$x \equiv 1 \pmod{2}$$, $$x \equiv 2 \pmod{3}$$, $$x \equiv 5 \pmod{17}$$, $$x \equiv 3 \pmod{5}$$;

Exercise 4.189 Solve the linear system of congruences.
$$x \equiv 0 \pmod{2}$$, $$x \equiv 0 \pmod{3}$$, $$x \equiv 1 \pmod{5}$$, $$x \equiv 6 \pmod{7}$$.

Exercise 4.190 Solve the linear system of congruences.

• $$x \equiv 4 \pmod{6}$$, $$x \equiv 13 \pmod{15}$$
• $$x \equiv 7 \pmod{10}$$, $$x \equiv 4 \pmod{15}$$
• $$x \equiv 7 \pmod{15}$$, $$x \equiv 4 \pmod{10}$$
• $$x \equiv 5 \pmod{6}$$, $$7x \equiv 3 \pmod{10}$$, $$4x \equiv 8 \pmod{15}$$
• $$x\equiv 1 \pmod{999},$$ $$x\equiv 2 \pmod{1001},$$ $$x\equiv 3 \pmod{1003},$$ $$x\equiv 4 \pmod{1004},$$ $$x\equiv 5 \pmod{1007}$$.

Exercise 4.191 Find the smallest even integer $$m$$ such that $$3|m$$, $$5|(m+3)$$, and $$11|(m+5)$$.

Exercise 4.192 Find three consecutive integers divisible by $$2, 3,$$ and $$5$$, respectively.

Exercise 4.193 Find a single congruence that is equivalent to the system of congruences $$x\equiv r_1 \pmod{m}$$ and $$x\equiv r_2 \pmod{m+1}.$$

Exercise 4.194 The three children in a family have feet that are 5 inches, 7 inches, and 9 inches long. When they measure the length of the dining room of their house using their feet, they each find that there are 3 inches left over. How long is the dining room?

Exercise 4.195 A professor feeds his pet python every fours days and bathes it once a week. This week he fed it on Tuesday and washed it on Wednesday. When if ever, will he feed and wash the Python on the same day? How often will this happen?

Exercise 4.196 A professor buys a new car every three years; he bought his first in 1981. He gets a sabbatical leave every seven years, starting in 1992. When will he first get both during a leap year?

Exercise 4.197 On the Fourth of July, a professor took a red pill at 8 a.m. and a green pill at noon. The next day he took a white pill at 10 p.m. He takes the red, green, and white pill every 5, 7, and 24 hours, respectively. How often does he take all three together? When in August will this first happen, if at all?

Exercise 4.198 If eggs are removed form a basket 2, 3, 4, 5, and 6, at a time, there remain, respectively, 1, 2, 3, 4, and 5 eggs. But if the eggs are removed 7 at a time, no eggs remain. What is the least number of eggs that could have been in the basket?

Exercise 4.199 Use the Chinese Remainder Theorem to solve the linear congruence equation $$3 x\equiv 11\text{ }(\text{mod} 245).$$

Exercise 4.200 Find three consecutive integers divisible by $$2, 3,$$ and $$5$$, respectively.

Exercise 4.201 Find the smallest even integer $$m$$ such that $$3|m$$, $$5|(m+3)$$, and $$11|(m+5)$$.

Exercise 4.202 Find a single congruence that is equivalent to the system of congruences $$x\equiv r_1 \pmod{m}$$ and $$x\equiv r_2 \pmod{m+1}$$. ::: {.solution } Solve the linear system of congruences $$x\equiv 2 \pmod{3}$$, $$x\equiv 5 \pmod{4}$$, $$x\equiv -3 \pmod{7}$$. We find $$N=(3)(4)(7)=84$$ and we use a table to construct the solution.
$\begin{array}{c|c|c|c|c} i & n_i & a_i & \bar{n}_i & u_i \\ \hline 1 & 3 & 2 & 84/3=28 & 28u_1\equiv 1 \pmod{3} \Longrightarrow u_1=1 \\ 2 & 4 & 5 & 84/4=21 & 21u_2\equiv 1 \pmod{4} \Longrightarrow u_2=1 \\ 3 & 7 & -3 & 84/7=12 & 12u_3\equiv 1 \pmod{7} \Longrightarrow u_3=3 \end{array}$ The solution is $x_0=(2)(28)(1)+(5)(21)(1)+(-3)(12)(3)=53 \pmod{84}.$

:::

Exercise 4.203 Using the Chinese Remainder Theorem, solve the system of linear congruence equations $$2x\equiv 3 (\text{mod} 4),$$ $$3x\equiv 5 (\text{mod} 6),$$ and $$4x\equiv 1 (\text{mod} 7).$$

Exercise 4.204 Solve the system $$2x\equiv 3 (\text{mod} 4),$$ $$5x\equiv 6 (\text{mod} 7),$$ $$9x\equiv 10 (\text{mod} 11)$$ using the Chinese Remainder theorem.