1.
Give the definition for these terms. Be sure to set up any notation that is required.
-
linear congruence
-
inverse of an integer modulo an integer
Exercises 5.4.4 Exercises
2.
State precisely the Chinese Remainder Theorem. Be sure to set up any notation that is required.
3.
State precisely the Fermat’s little theorem and Euler’s generalization. Be sure to set up any notation that is required.
4.
5.
6.
7.
Use Chinese Remainder Theorem> 5.4.2.1 to find the smallest positive solution to the system of congruences
\begin{equation*}
\left\{
{\begin{array}{l}
x \equiv 2 \pmod{3}\\
x \equiv 1 \pmod{4}\\
x \equiv 3 \pmod{5}
\end{array}}
\right\}.
\end{equation*}
8.
9.
Use Fermat’s little theorem to compute \(3^{302} \bmod{5}\text{.}\)
10.
Find all the solutions to
\begin{equation*}
\left\{
{\begin{array}{l}
x \equiv 2 \pmod{13}\\
x \equiv 6 \pmod {15}\\
\end{array}}
\right\}.
\end{equation*}
What is the smallest positive solution?
11.
Find all the solutions to
\begin{equation*}
\left\{
{\begin{array}{l}
x \equiv 2 \pmod{7}\\
x \equiv 3 \pmod{8}\\
x \equiv 4 \pmod{5}\\
\end{array}}
\right\}.
\end{equation*}
What is the smallest positive solution?
12.
The problems below are related. Namely, a computation in one portion may be used in more than one part.
-
Compute \(\gcd(2468, 357)\text{.}\)
-
Use the Extended Euclidean Algorithm to solve the Bézout equation for \(2468\) and \(357\text{.}\) Namely, find integers \(s\) and \(t\) such that\begin{equation*} \gcd(2468,357) = 2468 s + 357t. \end{equation*}
13.
14.
15.
Solve the linear congruence \(357 x \equiv 123 \pmod{2468}\text{.}\)
16.
I have an unknown number of Easter candies. When I arrange them in groups of \(20\text{,}\) there are \(3\) left over. When I arrange them in groups of \(41\text{,}\) there are \(26\) left over. What is the minimum number of candies that I could have?
17.
Solve the congruence \(2x \equiv 3 \pmod{13}\) by inspection.
18.
Solve the linear congruence \(19 x \equiv 11 \pmod{141}\text{.}\)
19.
Solve the congruence \(201x \equiv 5 \pmod{1357}\) using modular inverses.
20.
Split up the positive integers less than \(13\text{,}\) except \(1\) and \(12\) into pairs of integers such that each pair consists of integers that are inverses of each other modulo \(13\text{.}\) Use this to show \(12! \equiv -1 \pmod{13}\text{.}\)
21.
Suppose you collected shells on the beach with your daughter. When you arrange them in piles of \(15\text{,}\) there are \(13\) left over. When you arrange them in piles of \(19\text{,}\) there are \(6\) leftover. Use the Chinese Remainder Theorem to figure out how many shells you collected. Give the smallest positive solution.
