Q1

Let $a,b\in\Z^+$. We can find $q,r$ such that $a=qb+r$ where $0\le r < b$. Prove $(a,b)=(b,r)$.

Proof:

By definition: $(a,b)=ax+by=(xq+y)b+xr=(b,r)$ where $x,y,q \in \Z^+$. Therefore $(a,b)=(b,r)$

Q2

If $r\neq0$, we can find $b=q_1r+r_1$ with $0\leq r_1< r$. The process can be repeated, but only a finite number of steps are possible. Show $(r_k) = (a,b)$.

Proof:

At each step: $r_{m-1} = q_{m+1} r_m+ r_{m+1}$ where $0\le r_{m+1} < r_m$.

For each step, $r_{m}$ becomes progressively smaller with $r_{m+1} \leq r_m-1$ indicating a finite number of steps before stopping at $r_{m+1} = 0$.

Thus, by each step, we have:$(a,b)=(b,r)=(r,r_1)=...=(r_k,r_{k+1})$

Since $r_k = q_{k+2}r_{k-1}$, it follows $(r_k,r_{k+1}) = (r_k)$

Q4

Let $(a,b)=d$. For a function $am+bn=d$ , how to find m,n.

From Q2 we know: $r_{i+1} = r_{i-1} - r_iq_i$ . By substituting for $r_i$ from previous step until $r_{i+1} = am+bn$.

Q6

Let $a,b,c\in\Z$ and $ax+by=c$ has integers solutions iff $(a,b)|c$.

Proof:

If $ax+by=c$ have solution, it implies $c \in (a,b)$, so obviously $(a,b)|c$.

If $(a,b)|c$, then $c = c_0 * d$ where $(a,b)=d, a=pd,b=qd$. There must be a solution for $d = x_0a+y_0b$.

Q7

Let $d=(a,b)$ and $a=da',b=db'$, show that $(a',b')=1$.

Proof:

Assume $(a',b')=p$. Then $a'=mp$ and $b'=np$.

Thus $(a,b) = (mpd,npd) = (pd) = d$, which means $p = 1$.

Q8

If $x_0,y_0$ is a solution for $ax+by=c$. Show all solutions in form of $x_0,y_0$.

Proof:

Substitute $x,y$​ into the equation: $$a(x_0+t(b/d)) + b(y_0-t(a/d)) = ax_0+by_0+t(ab/d-ba/d) = ax_0+by_0=c$$

Q9

Suppose $u,v \in \Z$ and if $(u,v)=1, u|n,v|n$, then $uv|n$. If $(u,v)\neq 1$, that's not true.

Proof:

Since $u|n,v|n$, we can have $n=pu$, So $v|pu$. But $(u,v)=1$, hence $v|p$. Therefore $uv|pu$, which means $uv|n$.

If $(u,v) = g\neq1$, assume $u=ag,v=bg$. Let $n=abg$, we have $ag|abg,bg|abg$ which implies $u|n,v|n$. And $uv=abg^2 \nmid abg$.

Q10

Suppose $(u,v)=1$, show $(u+v,u-v)= 1\ \text{or}\ 2$

Proof:

Assume some value d such that $(u+v,u-v)=d$. Then $d|(u+v)$ and $d|(u-v)$

Thus we have: $$d|(u+v)+(u-v) \implies d|2u$$

$$d|(u+v)-(u-v) \implies d|2u$$

Since $(u,v)=1$, so $d|2$. That means $d=1\ \text{or}\ 2$

Q11

Show that $(a,a+k)|k$

Proof:

Assume $(a,a+k)=g$. We have $a=mg$ and $a+k=ng$ where $m,n\in \Z$.

Subtracting the two equation: $k= a+k-a = ng - mg = (n-m)g$ which means $g|k$

Q12

Show only six equilateral triangles, four squares and three hexagons are the only possibilities to form a evenly distributed common vertex.

Proof:

To form a common vertex, the angle of the polygon must sum to $360^\circ$. So we have $n$-sided polygon with $m$ of them, the internal angle is $\theta$ $$n\theta=(n-2)\pi$$

$$m\theta=2\pi$$

Solving this gives: $m=\frac{2n}{n-2}$.

Since m must be a positive integer, $(n-2)|2n$ is required.

The only solution is when $n=3,4,6$.

Q13

Let $n_1,n_2...n_s\in\Z$, and $(n_1,n_2,...,n_s)=d$. Prove that there exist integers $m_1,m_2,...,m_n$ such that $n_1m_1+n_2m_2+...+n_sm_s=d$.

Proof:

There exists a group of integers $p_1,p_2,...,p_s$ such that $n_1=p_1d,n_2=p_2d,...,n_s=p_sd$.

Since $(n_1,n_2,...,n_s)=d$, it follows that $(p_1,p_2,...,p_s)=1$, otherwise there would be a greater GCD for n.

Therefore, it is necessary that $p_1m_1+p_2m_2+...+p_sm_s=1$.

Hence $p_1m_1d+p_2m_2d+...+p_sm_sd=d$

Q14

Discuss the solvability of $a_1x_1+a_2x_2+...+a_nx_n=c$.

From Q14, it is solvable when $(a_1,a_2,...,a_n)|c$

Q15

Show that iff $\text{ord}_pa$ is even for all primes, we have a to be a square of another integer.

Proof:

Assume $a=b^2$.

$\text{ord}_pa=\text{ord}_pbb=\text{ord}_pb+\text{ord}_pb = 2\text{ord}_pb$

Therefore $\text{ord}_pa$ must be some value multiplied by 2, which is even.

Q16

If $(u,v)=1$, and $uv=a^2$, show $u,v$ are squares.

Proof:

By Q15 we know: $\text{ord}_pu + \text{ord}_pv = 2\text{ord}_pa$

Since $(u,v)=1$, it means $\text{ord}_pu,\text{ord}_pv$ cannot be non-zero simultaneously. Otherwise, there would be a $p$ as common divider.

Therefore $\text{ord}_pu,\text{ord}_pv$ are both even to all p. Thus they are squares.

Q17

Prove that $\sqrt{2}$ is irrational.

Proof:

Assume $\frac{p^2}{q^2}=2$, we have $p^2=q^2*2$

By Q15. We know if $p^2$ is a square number, that indicates $\text{ord}_2p^2$ is even. However, here it's 1. This is a contradiction.

Q18

Prove $\sqrt[n]{m}$ is irrational if $m$ is not a nth power of integer.

Proof:

Assuming $\frac{p^n}{p^n}=m$, we have $p^n=q^nm$.

That indicate $\text{ord}_nm$ should satisfy $\text{ord}_nm|n$.

Q19

Prove exist of Least Common Multiple (LCM) to be a smallest m that $a|m,b|m$ and for any other common multiple p, $m|p$.

Proof:

Assume $(a,b)=p$ and $a=sp,b=tp$.

We could have a LCM that $[a,b](a,b)=ab$ $$[a,b]=\frac{ab}{p}=\frac{stp^2}{p} = stp$$

Q20

1. Prove $\text{ord}_p[a,b]=\max(\text{ord}_p,\text{ord}_pb)$.

Proof:

By definition, there are $p^m|a,p^n|b$ and $p^{m+1}\nmid a,p^{n+1}\nmid b$.

It is known that, $p^{\max(m,n)}|[a,b]$.

If there exists $s>\max(m,n)$ such that $p^s|[a,b]$. It implies $p^s|a \ \text{or} \ p^s|b$ which is contradicts the assumption that $m,n$ are maximum value.

Therefore $\text{ord}_p[a,b]=\max(\text{ord}_p,\text{ord}_pb)$.

2. Prove $(a,b)[a,b]=ab$

Proof:

From Q19, we know $stp$ is one of the CM, we only need to prove that it is the least.

Assume $m$ is a common multiple of $a,b$. $m=ka=ksp$.

Since $b|m$ so $tp|ksp$, and given $[s,t]=1$, it follows that $t|k$. Thus, is $stp|m$, making our $stp$ the Least.

3. Prove $(a+b,[a,b])=(a,b)$

Proof:

$(a+b,[a,b])=am+bm+[a,b]n$ where $m,n\in\Z$.

Given, $[a,b]=sb=ta$ where $s,t\in\Z$.

So $(a+b,[a,b])=am+bm+[a,b]n=(m+nt)a+mb = ma+(m+sn)b=(a,b)$

Q21

Prove if $\text{ord}_pa\neq\text{ord}_pb$, $\text{ord}_p(a+b)\geq \min(\text{ord}_pa,\text{ord}_pb)$

Proof:

Let $p^\alpha|(a+b),p^m|a,p^n|b$ with the assumption that $m>n$.

We have $kp^\alpha=a+b,sp^m=a,tp^n=b$, where $\text{ord}_p(a+b)=\alpha,\text{ord}_pa=m,\text{ord}_pb=n,$that is $$kp^\alpha=sp^m+tp^n=p^n(sp^{m-n}+t)$$ Assume $\alpha < min(m,n)$, which implies $a < n$.

It follows that: $$k=p^{n-\alpha}(sp^{m-n}+t) \implies p|k$$ which is a contradiction that $p^\alpha|kp^\alpha$ and $p^{\alpha+1}\nmid kp^\alpha$.

Thus $\text{ord}_p(a+b)\geq \min(\text{ord}_pa,\text{ord}_pb)$.

Q23

If $a^2+b^2=c^2$, show that there exist $u,v$ that $c-b=2u^2,c+b=2v^2$ and $(u,v)=1$.

Proof:

Starting with $a^2=c^2-b^2 = (c+b)(c-b)$.

Assume both $c,d$ are either odd or even, $c+d=2x$ and $c-b=2y$ are both even.

It gives that $a^2=4xy$. Consequently $4|a^2$ and $2|a$.

Thus $4(a/2)^2=4xy$ implies $a^2/4=xy$.

Therefore $a/2=\sqrt{x}\sqrt{y}$. Since a is even, $\sqrt{x},\sqrt{y}\in Z$.

Q24

1. Prove that $x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+...+y^{n-1})$

Proof:

Base case for $n=1$: $x-y=x-y$.

Assume for $n=k$ and $x^k-y^k=(x-y)(x^{k-1}+x^{k-2}y+...+y^{k-1})$

For $n=k+1$: $$x^{k+1}-y^{k+1}=xx^k-yy^k=xx^k-yy^k+xy^k-xy^k=x(x^k-y^k)+y^k(x-y)$$

$$x^{k+1}-y^{k+1}=x(x-y)(x^{k-1}+x^{k-2}y+...+y^{k-1})+y^k(x-y)$$

$$x^{k+1}-y^{k+1}=(x-y)(x^k+x^{k-1}y+...+xy^{k-1}+y^k)$$

By Mathematical Induction, the statement is proved.

2. Prove for odd n, $x^n+y^n=(x+y)(x^{n-1}-x^{n-2}y+x^{n-3}y^2-...+y^{n-1})$

For $n=1$, it is trivially holds as $x+y=x+y$.

Assume $n=k$ and k is odd, the statement holds $x^k+y^k=(x+y)(x^{k-1}-x^{k-2}y+x^{k-3}y^2-...+y^{k-1})$

For $n=k+2$, we have $$x^{k+2}+y^{k+2}=x^2x^k+y^2y^k=x^2x^k+y^2y^k-x^2y^k+x^2y^k=x^2(x^k+y^k)+y ^k(y^2-x^2)$$

$$x^{k+2}+y^{k+2}=x^2(x+y)(x^{k-1}-x^{k-2}y+x^{k-3}y^2-...+y^{k-1})+y^k(y-x)(x+y)$$

$$x^{k+2}+y^{k+2}=(x+y)(x^{k+1}-x^ky+x^{k-1}y^2-...+x^2y^{k-1})+(x+y)(-xy^k+y^{k+1})$$

$$x^{k+2}+y^{k+2}=(x+y)(x^{k+1}-x^ky+x^{k-1}y^2-...+x^2y^{k-1}-xy^k+y^{k+1})$$

By Mathematical Induction, the statement is proved.

Q25

If $a^n-1$ is prime, show that $a=2$ and $n$ is prime.

Proof:

By Q24, we have $a^n-1=(a-1)(a^{n-1}+a^{n-2}+...+a+1)$.

Since the second part is always bigger than 1. So to make it prime, $(a-1)=1$ that is $a=2$.

Assume n is not prime, such that $n=pq$, and $p,q>1$. We have: $$2^{pq}-1=(2^p)^q-1=(2^p-1)((2^p)^{q-1}+(2^p)^{q-2}+...+2^p+1)$$ Since $2^p-1 > 1$, $2^{pq}-1$ is not prime. Thus n must be prime.

Q26

If $a^n+1$ is prime, show that a is even and n is a power of 2.

Proof:

First, if a is odd, $a^n+1$ is even which cannot be prime except 2.

Assume n is not power of 2. We shall consider n have at least one odd factor $p>1$.

We can write $n=pq$ where q is odd. $$(a^q)^p+1=(a^q+1)(a^{q-1}-a^{q-2}+a^{q-3}-...+1)$$ Since $a^q+1>1$ this implies $a^n+1$is not prime.

Therefore n must be a power of 2.

Q27

Prove that for all odd n, there is $8|(n^2-1)$.

Proof:

Given n is odd, we can express $(n^2-1)=(n+1)(n-1)$. Rewrite it as $n^2-1=2a*2b$, since $(n+1),(n-1)$ are both even.

Also, we know that $2a-2b=2(a-b)=2$ that is $a-b=1$

So one of $a,b$ must be odd and the other one is even.

Hence, we can rewrite again $n^2-1=2*2p*2b=8*pb$. So $8|(n^2-1)$

Prove that if $3\nmid n$, $6|(n^2-1)$.

Proof:

Same progress: $$n^2-1=(n+1)(n-1)$$ Since $3\nmid n$, $(n+1),(n-1)$ must have one of them be a multiple of 3, and the other is multiple of 2.

So $n^2-1=3x*2y=6xy$, that is $6|(n^2-1)$

Q28

Show that for all n, $30|n^5-n$ and $42|n^7-n$.

Proof:

This is Fermat's little theorem:

$5|n^5-n$, also $n^5-n=n(n+1)(n-1)(n^2+1)$ that $2|n^5-n, 3|n^5-n$. So $30|n^5-n$

$7|n^7-n$, also $n^7-n=n(n+1)(n-1)(n^2+n+1)(n^2-n+1)$ that $2|n^7-n, 3|n^7-n$. So $42|n^7-n$

Q29

If (a,b)=(c,d)=1, and $\frac{a}{b}+\frac{c}{d}$ is integer. Prove $b=d$

Proof:

Given $\frac{a}{b}+\frac{c}{d}=\frac{ad+cb}{bd}=p$ where p is integer.

It implies $ad=pbd-cb=b(pd-c)$. Since $(a,b)=1$ it follows that a does not contain any factor of b. That is d must be some multiple of b.

Same $bc-pbd-ad=d(pb-a)$, d must be some multiple of b.

So $b=d$.

Q30

Prove $\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+...+\frac{1}{n}$is not integer

Proof:

Consider a largest power of 2 number $2^s$ such that $2^s<n$.

When expressing the sum as $$\frac{\sum_{k=2}^n\frac{n!}{k}}{n!}$$ Consider the biggest power of 2 number $2^t$ that $2^t<n!$

Think about the numerator, the highest power of 2 that divides $n!/k$ is at least $t-s$.

So that means, the numerator will cancel out all even part so that must be an odd number.

Our sum will be like $\frac{\text{odd}}{\text{even}}$ making the sum a non-integer.

Q31

Prove that $(1+i)^2|2$ in $\Z[i]$

Proof:

$(1+i)^2*(-i)=2$

Q32

For $\alpha=a+bi$, $\lambda(\alpha)=a^2+b^2$. Show that $(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2$

Proof:

By $\lambda(\alpha\beta)=\lambda(\alpha)\lambda(\beta)$ $$\lambda(\alpha\beta)=(a+bi)(c+di)=(ac-bd)+（ad+bc)i$$

Q33

Show that $\alpha\in\Z[i]$ is a unit iff $\lambda(\alpha)=1$.

Proof:

$\alpha$ must divides 1 so it is called unit. That is $\alpha\beta=1$ .

If $\lambda(\alpha)>1$,$\lambda(\alpha\beta)=\lambda(\alpha)\lambda(\beta)=1$

$\lambda(\beta)<1$. Which is $c^2+d^2<1$, $c\ or\ d$ not integer.

So that for $a^2+b^2=1$, all possible combination is $a=\pm1,b=0$; $a=0,b=\pm1$

Q34

Show that $(1-\omega)^2|3$.

Proof: $$(1-\omega)^2(1+\omega)=(1-\omega)(1-\omega^2)=(1-\omega)(2+\omega)=2-\omega-\omega^2=3$$

Q35

Show Q33 works on $\Z[\omega]$

Proof:

Same $\lambda(\alpha\beta)=\lambda(\alpha)\lambda(\beta)=1$

$\lambda(\beta)<1$ leads to $c^2-cd+b^2<1$

That is $(c-d)^2+cd < 1$. The minimum of $(c-d)^2=0$, so $c,d\in\Z$ $cd>1$. Contradiction.

When $(c-d)^2+cd=1$, the only possible combination of c,d is $c=\pm1,d=0;c=0,d=\pm1;c=1,d=-1;c=-1,d=1$

Q36

Show $\Z[\sqrt{-2}]$ that in form of $a+b\sqrt{-2}$ is a ring and is a Euclidean domain.

Proof:

Consider $\alpha=a+b\sqrt{-2}$ and $\beta=c+d\sqrt{-2}$. $$\frac{\alpha}{\beta}=\frac{\alpha\bar\beta}{\lambda(\beta)}=\frac{(a+b\sqrt{-2})(c-d\sqrt{-2})}{c+2d^2}=\frac{ac+2bd}{c+2d^2}+\frac{bd-ad}{c+2d^2}\sqrt{-2}$$ That is $$\alpha\beta^-1=(q_1+q_2\sqrt{-2})+(r_1+r_2\sqrt{-2})=r+s\sqrt{-2}$$

$$\alpha=\beta(q_1+q_2\sqrt{-2})+\beta(r_1+r_2\sqrt{-2})$$

$$\lambda(\beta(r_1+r_2\sqrt{-2}))=\lambda(\beta)(r_1^2+2r_2^2)\leq\frac{3}{4}\lambda(\beta)\leq\lambda(\beta)$$

Q37

Show the only unit in $\Z[\sqrt{-2}]$ is 1and -1:

Proof:

$a^2+2b^2=1$ the only possibility is $a=\pm1,b=0$

Q38

Suppose that $\pi \in \Z[i]$ and $\lambda(\pi)$ is prime in $\Z$. Show that $\pi$ is also prime in $\Z[i]$. This also holds in $\Z[\omega]$ and $\Z\sqrt{-2}$

Proof:

Assuming for contradiction that $\pi$ is not prime in $\Z[i]$. Meaning there exsit $\alpha.\beta$ such that $\pi=\alpha\beta$, and neither $\alpha$ nor $\beta$ being units or associates with $\pi$.

Then by the norm function, $\lambda(\pi)=\lambda(p\alpha)=\lambda(p)\lambda(\alpha)$. That indicate that $\lambda(\pi)$ is not prime because neither $\alpha$ nor $\beta$ being units.

The reason extends analogously to $\Z[\omega]$ or $\Z[\sqrt{-2}]$.

Q39

Prove that in any integer domain, the prime is irreducible.

Proof:

Assume a prime $p \in D$ is not irreducible. That means $p=ab$ , $a,b\in D$ and $a,b$ are not unit.

Since p is prime, p should divide a or b.

That is $a=p*c$

So we have $p=ab=p(bc)$. Which shows that $bc$ is unit. That leads to $b$ is unit which is a contradiction.