Number Theory

Questions 1.1, 1.3, 1.11, 1.12, 1.14, 1.18, 1.21, 1.26, 1.27.

1.1 Proof: There exist integers h and k such that ah = b and ak = c. It follows that ah+ak = a(h+k)=b+c, so a divides b+c.

1.3 Proof: There exists an integers h such that ah = b, multiply both sides by c, we get ahc = bc, so a divides bc. 1.11 Proof: There exist integers h and k such that a-b = hn and b-c = kn. It follows that a-c = (a-b)+(b-c) =hn + kn + (h+k)n, so a ≡ c (mod n). 1.12 Proof: There exist integers h and k such that a-b =hn and c-d = kn, add there equations, we get (a+c)-(b+d) =(a-b)+(c-d)=hn+kn=(h+k)n, a+c≡b+d (mod n). 1.14 Proof: There exist integers h and k such that a-b =hn and c-d = kn. It follows that a = b+hn and c =d+kn, multiply these equations, we get ac = (b+hn)(d+kn)=bd + (bk +dh+khn)n, this says that ac-bd is divisible by n, hence ac ≡ bd (mod d). 1.18 Proof: we prove the theorem by induction. The theorem certainly holds for k=1, and we will assume it is true for some integer k. From theorem 1.14, we know that a ≡ b (mod n) and ak ≡ bk (mod n) together imply that aak ≡ bbk (mod n), equivalently, ak+1 ≡ bk+1 (mod n). This shows the theorem is true for k+1, we complete the induction step. 1.21 Proof: We write n = ak*10k+ ak-1*10k-1 +…+a1*10+a0 = ak(10k-1)+ak-1(10k-11)+…+a1(10-1)+(ak+ak-1+…+a1+1) = ak(10k-1)+ak-1(10k-1-1)+…+a1(10-1) + m. Since 9 |10 k -1 hence 3|10k-1 for any positive integer k, this shows that n ≡ m (mod 3), our theorem follows. 1.26 Proof: We begin by defining the set S ={m-xn|x an integer; m-xn ≥ 0} . Since 0 belongs to S, the set S is nonempty. Now by the Well-Ordering Principle, we infer that the set S contains a smallest interger r. By the definition of S, there exists an integer q satisfying r = m-qn≥0. We claim that r