Q1

Prove there are infinitely many primes such that $p \equiv -1 (6)$.

Proof:

We need to prove there are infinitely many prime such that $6|(p+1) \implies p = 6k -1$

Assume there are finite primes such that $p = 6k-1$. There will be a new prime $q=6(p_1p_2...p_n)-1$. This shows q is yet another prime. So there are infinitely many primes.

Q3

For a series $a_i$, we can represent any decimal in $\sum_{i=0}a_i10^i$. Prove that if $3|\sum_{i=0}a_i$ or $9|\sum_{i=0}a_i$ ,the decimal will be divisible by 3 or 9. Also true for $11|\sum_{i=1}(-1)^ia_i$.

Proof:

It is obviously that $10^i \equiv 1(3)$ and $10^i \equiv 1(9)$. And $a_i10^i \equiv a_i (3)$. So if $\sum a_i 10^i \equiv \sum a_i (3)$.

Also $10 \equiv 10 (11)$ and $100 \equiv 1 (11)$ that is $10^i \equiv (-1)^i (11)$.

Q4,5

Prove $3x^2+2=y^2$ and $7x^3+2=y^3$ have no solutions.

Proof

Consider $$3x^3 +2 \equiv y^2 (3)$$ We already have $3x^2 \equiv 0 (3)$, so $2 \equiv y^2 (3)$.

For mod 3, we have $0^2 \equiv 0 (3), 1^2 \equiv 1 (3), 2^2 \equiv 1(3)$. So $y^2 \equiv 2 (3)$ is impossible.

Consider $$7x^3 + 2 \equiv y^3 (7)$$ We need to show $2 \equiv y^3(7)$.

It is impossible cause $y^3 (7)$ is $0,1,6$.

Q6

If a group integers $a_1,a_2,a_3,...,a_{\phi(n)}$ such that $(a_i,n)=1$. We will have $(a,n)=1$ and $aa_1,aa_2,...,aa_{\phi(n)}$ such that $(aa_i,n)=1$.

Proof:

It is obvious that $(a,n)=1, (b,n)=1 \implies (ab,n)=1$.

On the other hand, assume a $U(n)=\{a_1,a_2,...,a_{\phi(n)}\}$. $\{aa_i\}$ is just a permutation of $U(n)$.

Q7

Prove Euler's Theorem.

Proof:

Assume $A = a_ia_2a_3...a_{\phi(n)}$ and $a^{\phi(n)}A = aa_1aa_2...aa_{\phi(n)}$. That is $$

By Q6: $a^{\phi(n)}A \equiv A (n)$. Also since $(A,n)=1$, so it's safe to cancel A on both side. $$a^{\phi(n)} \equiv 1 (n)$$

Q8

Let $p$ is an odd prime. If $k\in \{1,2,...,p-1\}$, there will be a unique $b_k$ such that $kb_k\equiv1(p)$.

Proof Since p is prime, we have $(k,p)=1$.

So by Fermat's little theorem: $$k^{p-1}\equiv 1 (p)$$ So we have a solution $b_k = k^{p-2}$

Assume there are another solution $kb_k'\equiv 1(p)$. $$k(b_k - b'_k) \equiv 0 (p)$$ That is $p|(b_k - b_k')$ which is unique in mod p system, thus $b_k-b'_k=0$​.

In this way, when $k\neq 1, k\neq p-1$, $k\neq b_k$.

Q9

Prove $(p-1)!\equiv -1(p)$.

Proof:

From Q8, we know that there are pairs in $1,2...p-1$. For each pair, we have $kb_k\equiv 1(p)$. Except $k=1,k=p-1$. Since $p-1 \equiv -1 (p)$.

So $(p-1)!\equiv -1(p)$.

Q10

Prove $(n-1)!\equiv0(n)$ if n is not prime, except when $n=4$.

Proof:

In general, $n=ab$ where $a<n,b<n$. So $ab|(n-1)!$

When $n=4$, $(n-1)! = 1*2*3=6$. So $6 \equiv 2 (4)$. The reason 4 is an exception is that the only composition $4=2*2$ and 2 is only shown once in $3!$.

Q11

For a reduced residue system modulo $n$: $\{a_1,a_2,...,a_{\phi(n)}\}$. Assume $N$ is the number of solutions of $x^2 \equiv 1(n)$. Show that $a_1a_2...a_{\phi(n)}\equiv (-1)^{N/2}(n)$.

Proof:

By Wilson's Theorem in Q9, we can notice that in a reduced residue system, for each $k\in\{a_i\}$, we will have a $b_k$ as it's inverse so $kb_k\equiv 1(n)$, except when $k^2\equiv1(n)$​.

Consider $n=\prod p_i^{a_i}$.

Given that each $p_i^{a_i}$ will provide a residue system modulo that $\prod a_i \equiv -1 (n)$ since $k^2 \equiv 1(n)$ will provide 2 solutions $(1,n-1)$. When $n=2$, the product will be 1, that will not affect anything.

Then there will be $(-1)^{N/2}$ .

Q12

Prove that $p|\binom{p}{k}$, $0<k<p$

Proof:

By definition: $$\binom{p}{k} = \frac{p!}{k!(p-k)!}$$ Since $p!=(p-1)!*p$. And p is prime. So no factors in $k!(p-k)!$ since $k<p,p-k<p$. So $p$ in upper fraction must remain. That is $p|\binom{p}{k}$

Q13

Prove Fermat's Theorem

Proof:

By Q12, consider : $$(a+1)^p - a^p -1= \sum_{k=1}^{p-1}\binom{p}{k}a^{p-k}$$ Since we know that $p|\binom{p}{k}$ so each part in the sum can be divided by p.

That is: $$(a+1)^p \equiv a^p+1 (p)$$ When $a=0$, obviously $1\equiv 1 (p)$ .

When $a > 0$, assume $a^p \equiv a (p)$ (Fermat). We need to prove for $a+1$ it still hold. $$(a+1)^p \equiv a + 1(p)$$ Since we already have $a^p \equiv a(p)$. So: $$(a+1)^p \equiv a^p +1 (p)$$ That is just we proved before.

So Fermat's Theorem holds.

Q14

For $p,q$ are distinct odd primes such that $p-1|q-1$. Also if $(n,pq)=1$, prove that $n^{q-1}\equiv 1(pq)$.

Proof:

By Fermat's Theorem: $$n^{p-1} \equiv 1 (p)$$

$$n^{q-1} \equiv 1(q)$$

Where $n^{q-1}=n^{k(p-1)}$

So we have $$n^{q-1} \equiv 1 (p)$$ That gives: $$n^{q-1} \equiv 1 (pq)$$

Q15

Prove the numerator of $1+1/2+1/3...1/p-1$ is divisible by $p$ where p is prime.

Proof: $$\text{numerator} = \sum_{i=2}^{p}\frac{p!}{i}$$ Obviously, each term is still integer and all divisible by p.

Q17

Prove for $f(x) \in \Z[x]$ and $n=\prod p_i^{a_i}$, prove that $f(x) \equiv 0 (n)$ has a solution iff $f(x) \equiv 0 (p_i^{a_i})$ has solution for all $i$

Proof:

If $f(x)\equiv 0 (n)$, we have $n|f(x)$. So for all $p_i^{a_i}|f(x)$ that is $f(x) \equiv 0 (p_i^{a_i})$

If $f(x) \equiv 0 (p_i^{a_i})$, by Chinese Reminder Theorem, $(p_i^{a_i},p_j^{a_j})=1$, then $f(x) \equiv 0 (\prod p_i^{a_i})$ have a unique solution.

Q18

If there are $N_i$ solutions for $f(x) \equiv 0 (p_i^{a_i})$. Then there are $\prod N_i$ solutions for $f(x) \equiv 0(n)$.

Proof:

By Chinese Reminder Theorem, for each group of equations: $$\{x \equiv x_i (p_i^{a_i})\}$$ There are one unique solution. So there are $\prod N_i$ different equations set. So there are $\prod N_i$ unique solutions for $f(x) \equiv 0 (n)$

Q19

Show that $x^2\equiv 1(p^a)$ has only solutions $\{1,-1\}$.

Proof:

We need to show the solution of: $$(x+1)(x-1) \equiv 0 (p^a)$$ The difference of $(x+1),(x-1)$ is 2, which is smaller than any $p^a$.

That is, $(x+1)(x-1)$ cannot contain more than 1 p as factor.

That is, there are only 2 solution $x=1,x=-1$.

Q20

Show that $x^2\equiv 1(2^b)$ has one solution when $b=1$ and 2 solution when $b=2$ and four solution when $b\geq3$.

Proof: $$(x+1)(x-1)\equiv 0(2^b)$$ When $b=1$, $\{1,-1\}$ are same solutions in mod 2.

When $b=2$, $\{1,-1\}$ two solutions.

When $b\geq3$, $(x-1),(x+1)$ can be two even number in sequence. So when $x=2^{b-1}-1$ or $x = 2^{p-1}+1$ will also be valid solutions.

Q21

Find the number of solutions $x^2 \equiv 1(n)$

Proof:

For the factorization of n $n = \prod p_i^{a_i}$.

Assume $\nu(p_i^{a_i})$ is the solution number of $x^2 \equiv 1 (p_i^{a_i})$.

For $p_i=2$ $$\nu(2) =1; \nu(2^2)=2; \nu(2^a)=3, a \geq 3$$ For other $p_i$, $\nu(p_i^{a_i})=2$.

So the solution will be: $$\nu(n) = \prod \nu(p_i^{a_i})$$

Q23

Prove $a+bi \equiv 0 (1+i)$ or $a+bi \equiv 1 (1+i)$

Proof:

Assume $p+qi$ such that: $$(p+qi)(1+i) = a+bi$$

$$(\frac{a+b}{2}+\frac{b-a}{2})(1+i)=a+bi$$

So when $a+b$ and $b-a$ are both even, there are $a+bi \equiv 0 (1+i)$

Assume $p+qi$ such that: $$(p+qi)(1+i)=a-1+bi$$

$$(\frac{a+b-1}{2}+\frac{b-a+1}{2}i)(1+i)=a-1+bi$$

So when $a+b$ and $b-a$ are odd, we have $a+bi\equiv 1(1+i)$

If $a,b$ are both even, $a+b$ and $b-a$ shall both be even.

If $a,b$ are both odd, $a+b$ and $b-a$ shall both be even.

In other situation, $a+b$ and $b-a$ shall both be odd.

Q24

Prove $a+b\omega \equiv \{-1,1,0\} (1-\omega)$

Proof:

By definition $\omega^2+\omega+1=0$. $$\omega \equiv 1 (1-\omega)$$

$$a+b\omega \equiv a+b (1-\omega)$$

So this can be represent to any congruences.

The order of $1-\omega$ is $(1-\omega)(1+\bar\omega) = (1-\omega)(1-\omega^2)=2-\omega-\omega^2=3$

So this is equal to $\text{mod}\ 3$: $\{0,1,2\}$

Where $2 \equiv -1 (3)$

Q25

For $\lambda = 1-\omega$, $\alpha \equiv 1(\lambda)$, prove that $\alpha^3 \equiv 1(9)$

Proof:

First we shall see: $$-\omega^2(1-\omega)^2 = -3\omega(1+\omega)=3$$ Then we assume: $$\alpha = 1+\lambda$$

$$\alpha^3 = 1 + 3\lambda + 3\lambda^2 + \lambda^3$$

$$\alpha^3 = 1 - \omega^2\lambda^3 -\omega^2\lambda^4 + \lambda^3$$

We need to show that the last three part is divisible by 9. $$\lambda^4 = 9\omega^2; \lambda^3 = -3(2\omega+1)$$ So we need to prove that $$3|-(1 - \omega^2)(2\omega+1)$$ Obviously $-(\omega+2)(2\omega+1)=3\omega$

Q26

For $\zeta,\eta,\xi \in \Z[\omega]$ such that $\eta^3 + \zeta^3 + \xi^3 = 0$ , $\lambda$ must divides at least one of them.

Proof:

It is obvious there are only 3 reminder for $\alpha \equiv \{1,-1,0\}(\lambda)$.

By Q25, $\alpha^3 = 9k + \{1,-1,0\}$

So $\eta^3 + \zeta^3 + \xi^3 = 0$ is equivalent to $\eta + \zeta + \xi = 0$

That is at least one of them is $\eta \equiv 0 (\lambda)$