problem 1. 1. (24 points). Find, with proof, all integers $x$ with $0 \leq x \leq 301$ with
$$
21 x \equiv 161 \quad(\bmod 301)
$$
Do not use a calculator on this problem.
Proof.
$$
\begin{aligned}
21 x \equiv 161(\bmod 301) & \Longleftrightarrow 15 \cdot 21 x \equiv 15 \cdot 161 \equiv 2415(\bmod 301) \
& \Leftrightarrow 305 x \equiv 2415(\bmod 301) \
& \Leftrightarrow 4 x \equiv 7(\bmod 301) \
& \Leftrightarrow 4 \cdot 75 x \equiv 7 \cdot 75(\bmod 301) \
& \Leftrightarrow-x \equiv 224(\bmod 301) \
& \Leftrightarrow x \equiv 77(\bmod 301)
\end{aligned}
$$
because $0 \leq x \leq 301$, so $x=77$
problem 2. 2. (24 points). Find the smallest positive integer $r$ so that
$$
111^{94} \equiv r \quad(\bmod 79)
$$
You may not use a calculator, but you may use the fact that 79 is prime.
Proof.
$$
\begin{aligned}
114^{94} & \equiv r(\bmod 79) \
\Rightarrow r &\left.\equiv(35)^{94}(\bmod 301) 79\right)
\end{aligned}
$$
becomse 79 is a prime. So by farmat litte theorem
$$
\begin{array}{c}
(35)^{78} \equiv 1(\bmod 79) \
\text { so } r \equiv 35^{16} \equiv(1125)^{8} \equiv(1125-1106)^{8} \equiv 19^{8} \equiv 36^{4} \equiv 45^{4} \equiv 2025^{2}(\bmod 79) .
\end{array}
$$
We know $2025 \equiv 2025-79 \cdot 25 \equiv 2025-1975 \equiv 50(\bmod 79)$
$$
\text { So } r \equiv 50^{2} \equiv 2500 \equiv 2500-31 \cdot 79 \equiv 2500-2449 \equiv 51(\bmod 79)
$$
So the mallest positive integer so that $111^{94} \equiv r \quad(\bmod 79)$ is $r=51$.
problem 3. 3. (24 points). Find the unique positive integer $n$ with $1 \leq n \leq$ 1000 so that
$$
\begin{array}{ll}
n \equiv 2 & (\bmod 7) \
n \equiv 3 & (\bmod 11) \
n \equiv 5 & (\bmod 13) .
\end{array}
$$
Do not use a calculator.
Proof. If we ean find $x, y, z$ satisfied
$
\left{\begin{array}{l}
11 \cdot 13 \cdot x \equiv 1(\bmod 7) \
7 \cdot 13 \cdot y \equiv 1(\bmod 11) \
7 \cdot 11 z \equiv 1(\bmod 13)
\end{array}\right.
$
then it is easy to check
$\left{\begin{array}{l}n \equiv 2(\bmod 7) \ n=3(\bmod 11) \ n \equiv 5(\bmod 13))\end{array}\right.$
So the problem reduce to find $x . y . z$
such that
$$
\begin{array}{c}
\text { in fact } \quad x \cdot 143 \equiv 1(\bmod 7) \Rightarrow 3 \cdot x \equiv 1(\bmod 7)) \Rightarrow x \equiv 5(\bmod 7) \
y \cdot 91 \equiv 1(\bmod 11) \Rightarrow 3 y \equiv 1(\bmod 11) \Rightarrow y \equiv 4(\bmod 11) \
z \cdot 77 \equiv 1(\bmod 13) \Rightarrow 12 \cdot z \equiv 1(\bmod 13) \Rightarrow z \equiv 12(\bmod 13)
\end{array}
$$
So when $n \equiv 2 \cdot 11 \cdot 13 \cdot 5+3 \cdot 7 \cdot 13 \cdot 4+5 \cdot 7 \cdot 11 \cdot 12 \equiv 7142 \equiv 135(\bmod 1001)$
we know $n$ satisfied the condition, so $n=135$ is the unique positive number $n$ satisfied the condition
problem 4. 4. (24 points). Let $d=$ ged $\left(2528^{2767}-1,4072^{1601}-1\right)$. Prove that if $q$ is a prime divisor of $d$, then $q \equiv 1(\bmod 2767 \cdot 1601)$. You may use that ged $(2527,4071)=1$ and that 2767 and 1601 are primes, but do not use a calculator or computer for computations.
Proof. assume $2767=p_{1} \quad 1601=p_{2} \quad 2527=x \quad 4071=y$
how $q$ is a prime and $q\left|(x+1)^{p_{1}}-1, \quad q\right|(y+1)^{p_{2}}-1$ because $g(d(x, y)=1$ so $q|x, q| y$ can hot hold at the same time.
Case $\mathrm{A}(q, x y)=1$, in this case, we prove $q \equiv 1\left(\bmod p_{1} p_{2}\right) .$
in fact, consider $a$ is the smallest integer s.t. $q \mid x^{a}-1$, because $(q, x)=1$, so $a \geq 2$, now, $q\left|x^{a}-1, q\right| x^{p_{1}}-1$, so we have $q \mid x^{g c d\left(a, p_{1}\right)}-1$
because $\operatorname{gcd}(p, a) \leqslant \min \left{a p_{1}\right}$ and by the choose of $a$ we know $p_{1}=a$. and on the other hand by farmat little theorem, $d \mid x^{d-1}-1$ (because $d$ is a prime). so $p_{1} \mid d-1$ i.e. $d \equiv 1\left(\bmod \quad p_{1}\right)$ by the same argument we know $d \equiv 1\left(\bmod \quad p_{2}\right)$,
$$
\text { so } d \equiv 1\left(\bmod \quad p_{1} p_{2}\right)
$$
Case B. $q \mid x$ or $q \mid y$ in this case there exist counterexample we can only prove $d \equiv 1\left(\bmod p_{1}\right)$ or $d \equiv 1\left(\bmod p_{2}\right)$
problem 5. 5. (24 points). Let $k$ be a positive integer. Prove that there is some positive integer $n$ so that $k \cdot 3^{n}+1$ is composite.
Proof. assume there do hot exist positive number $n$ so that $k \cdot 3^{n}+1$ is composite. then for all $n \in N^{} . k \cdot 3^{n}+1$ is a prime. now arbitrang chose a positive number $n_{0} \in \mathbb{N}^{}$ and assume $k \cdot 3^{n_{0}}+1=p_{0} . \quad p_{0}$ is $a$ prime.
then $\left(3, p_{0}\right)=\left(3, k \cdot 3^{n_{0}}+1\right)=(3,1)=1$ so by farmat little theorem
$$
3^{p_{0}-1} \equiv 1\left(\bmod p_{0}\right)
$$
so
$$
k \cdot 3^{n_{0}+p_{0}-1}+1 \equiv k \cdot 3^{n_{0}} \cdot 3^{p_{0}-1}+1 \equiv k_{3}^{n_{0}}+1 \equiv 0\left(\bmod p_{0}\right)
$$
i.e. $p_{0} \mid k \cdot 3^{n_{v}+p_{0}-1}+1 .$ but $\quad p_{0}=k \cdot 3^{n_{0}}+1<k \cdot 3^{h_{0}+p_{0}-1}+1$ So
$k \cdot 3^{n_{0}+p_{0}-1}+1 \quad$ is composite. this contract with the previous assume so there exist some positive integer $n$. so that $k \cdot 3^{n}+1$ is composite.
