# A COMPUTATIONAL INTRODUCTION TO NUMBER THEORY AND ALGEBRA by VICTOR SHOUP By VICTOR SHOUP

Best algebra books

Algebra VII: Combinatorial Group Theory Applications to Geometry

From the experiences of the 1st printing of this booklet, released as quantity fifty eight of the Encyclopaedia of Mathematical Sciences:". .. This booklet might be very priceless as a reference and consultant to researchers and graduate scholars in algebra and and topology. " Acta Scientiarum Mathematicarum, Ungarn, 1994 ". .

Additional resources for A COMPUTATIONAL INTRODUCTION TO NUMBER THEORY AND ALGEBRA (VERSION 1)

Sample text

Make sure your algorithm correctly computes the sign bit of the result, and also strips leading zero digits from the result. 15. Work out the details of an algorithm that compares two signed integers a and b, determining which of a < b, a = b, or a > b holds. 16. Suppose that we run the division with remainder algorithm in Fig. 1 for > 1 without normalizing b, but instead, we compute the value qi in line 4 as follows: qi ← (ri+ B 2 + ri+ −1 B + ri+ −2 )/(b −1 B +b −2 ) . Show that qi is either equal to the correct quotient digit, or the correct quotient digit plus 1.

4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. for i ← 0 to k − 1 do ri ← ai rk ← 0 for i ← k − down to 0 do qi ← (ri+ B + ri+ −1 )/b −1 if qi ≥ B then qi ← B − 1 carry ← 0 for j ← 0 to − 1 do tmp ← ri+j − qi bj + carry (carry, ri+j ) ← divmod(tmp, B) ri+ ← ri+ + carry while ri+ < 0 do carry ← 0 for j ← 0 to − 1 do tmp ← ri+j + bi + carry (carry, ri+j ) ← divmod(tmp, B) ri+ ← ri+ + carry qi ← qi − 1 output the quotient q = (qk− · · · q0 )B and the remainder r = (r −1 · · · r0 )B Fig. 1. Division with Remainder Algorithm Finally, consider the general case, where b may not be normalized.

Let a, b, n ∈ Z with n > 0, and let d := gcd(a, n). If d | b, then the congruence az ≡ b (mod n) has a solution z, and any integer z is also a solution if and only if z ≡ z (mod n/d). If d b, then the congruence az ≡ b (mod n) has no solution z. Proof. For the ﬁrst statement, suppose that d | b. 6, and the fact that a/d and n/d are relatively prime. For the second statement, we show that if az ≡ b (mod n) for some TEAM LinG 18 Congruences integer z, then d must divide b. To this end, assume that az ≡ b (mod n) for some integer z.