number_theory_4_10-2-1

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.

## 数论代写

Categories: 数学代写数论