文档介绍：Supplementary Material: putational Introduction to Number
Theory and Algebra (Version 1)
Last updated: 10/19/2005.
This document contains supplementary exercises, examples, and a few alternative proofs
of theorems that would make nice additions to the book, and may be added in a later edition.
Section
After proof of Theorem , the following text might be helpful:
Theorem can be visualized as follows:
r
0 b 2b 3b a 4b
Starting with a, we subtract (or add, if a is negative) the value b until we end
up with a number r in the interval {0, . . . , b − 1}.
We can also add the following as an exercise in this section:
Exercise 1. Generalize Theorem as follows. Let a, b ∈ Z with b > 0. Let x, y be real
numbers such that y −x = b. Show that there exist unique q, r ∈ Z such that a = bq +r and
r ∈[x, y). Show the same, but for the interval (y, x]. Does the statement hold in general
for the intervals [x, y] or (x, y)?
Section
Exercise 2. Let a, n1, . . . , nk be integers. Show that gcd(a, n1 · · · nk) = 1 if and only if
gcd(a, ni) = 1 for i = 1, . . . , k.
Section
After Exercise :
Exercise 3. Generalize Exercise to odd prime powers. Specifically, show that if p is an
odd prime and e is a positive integer, then x2 ≡ 1 (mod pe) implies x ≡±1 (mod pe). Also
show that the corresponding statement is false for p = 2. Hint: to prove the statement for
odd p, show that if (y + )2 ≡ 1 (mod pe), where p | y and = ±1, then pe | y.
1
Section
Before Exercise :
Exercise 4. Let n be a positive integer, let a be any integer, and let d := gcd(a, n). Show
that the number of integers b ∈{0, . . . , n − 1} such that the congruence
az ≡ b (mod n)
has some integer solution z is equal to n/d, and that for any such b, the number of integers
z ∈{0, . . . , n − 1} satisfying the congruence is equal to d.
Section
Exercise . Qk
5 Let n1, . . . , nk be positive integers, and let n := i=1 ni. Consider the map
Z Z Z