posted 6 Jan 2022

Chapter 1 Exercises

Notes Number Theory Chapter 1 Exercises

§ Exercise 1

Problem: Let aa and bb be nonzero integers. We can find nonzero integers qq and rr such that a=qb+r,a = qb + r, where 0≤r<b.0 \leq r \lt b. Prove that (a,b)=(b,r).(a, b) = (b, r).

Solution: Clearly a∣qb+r.a | qb + r. Let dd be the gcd of aa and b.b. Because d∣a,d | a, we get d∣qb+r,d | qb + r, so d∣qbd | qb and d∣r.d | r.

As a result, any common divisor of aa and bb is also a divisor of r.r. Because r<b,r \lt b, there can be no common divisor between bb and rr greater than those of aa and b.b. Therefore, (a,b)=(b,r).(a, b) = (b, r).

§ Exercise 2

Problem: (this is a continuation to ex. 1)

If r≠0,r \neq 0, we can find q1q_1 and r1r_1 such that b=q1r+r1b = q_1r + r_1 with 0≤r1<r.0 \leq r_1 \lt r. Show that (a,b)=(r,r1).(a, b) = (r, r_1).

This process can be repeated.

Show that it must end in finitely many steps. Show that the last nonzero remainder must equal (a,b).(a, b).

Solution: We've proved this in my cryptography class, see theorem 3.1 under the Euclidean algorithm.

§ Exercise 3

Skipped.

§ Exercise 4

Problem Let d=(a,b)d = (a, b) show that the Euclidean algorithm can be used to find mm and nn such that am+bn=d.am + bn = d.

Solution: The process is outlined under the Bézout Coefficients section from my cryptography notes.

§ Exercise 5

Skipped.

§ Exercise 6

Problem: Let a,b,c∈Z.a, b, c \in \mathbb{Z}. Show that the equation ax+by=cax + by = c has integer solutions iff (a,b)∣c.(a, b) | c.

Solution: Let d=(a,c).d = (a, c).

(⇒\Rightarrow) We can see that dd divides the left hand side which means that dd must divide c.c.

(⇐\Leftarrow) Sps. d∣cd | c so c=dc′c = dc' for some c′∈Z.c' \in \mathbb{Z}. Then we can write au+bv=dau + bv = d for some m,n∈Z.m, n \in \mathbb{Z}. Then by multiplying the expression by c′c' we get auc′+bvc′=dc′=c.auc' + bvc' = dc' = c. Finally let x=uc′x = uc' and y=vc′y = vc' be integer solutions to ax+by=c.ax + by = c.

§ Exercise 7

Problem: Let d=(a,b)d = (a, b) and a=da′a = da' and b=db′.b = db'. Show (a′,b′)=1.(a', b') = 1.

Solution: Let d′=(a′,b′),d' = (a', b'), so d′∣a′d' | a' and d′∣b′.d' | b'. Then dd′∣add' | a and dd′∣b.dd' | b. If d′≠1d' \neq 1 then dd′dd' is a common divisor of aa and bb that is larger than d.d.

§ Exercise 8

Problem: Let x0x_0 and y0y_0 be a solution to ax+by=c.ax + by = c. Show that all solutions have the form x=x0+t(b/d),y=y0−t(a/d)x = x_0 + t(b / d), y = y_0 - t(a / d) where d=(a,b)d = (a, b) and t∈Z.t \in \mathbb{Z}.

Solution: To be completed.