138
Proofs, Induction, and Number Theory
//j now has the value x
2
return j
end function Square
Q: j = i
2
5. Function to return the value of x
y
for x, y ≥ 1.
Power (positive integer x, positive integer y)
Local variables:
integers i, j
i = 1
j = x
while i ≠ y do
j = j ∗ x
i = i + 1
end while
//j now has the value x
y
return j
end function Power
Q: j = x
i
6. Function to compute and write out quotient q and remainder r when x is divided by y, x ≥ 0, y ≥ 1.
Divide (nonnegative integer x; positive integer y);
Local variables:
nonnegative integers q, r
q = 0
r = x
while r ≥ y do
q = q + 1
r = r – y
end while
//q and r are now the quotient and remainder
write(“The quotient is” q “and the remainder is” r)
end function Divide
Q: x = q ∗ y + r
For Exercises 7–12 use the Euclidean algorithm to find the greatest common divisor of the given numbers.
7. (308, 165)
8. (2420, 70)
9. (735, 90)
10. (8370, 465)
11. (1326, 252)
12. (1018215, 2695)
13. Following is the problem posed at the beginning of this chapter.
The nonprofit organization at which you volunteer has received donations of 792 bars of soap and
400 bottles of shampoo. You want to create packages to distribute to homeless shelters such that
each package contains the same number of shampoo bottles and each package contains the same
number of bars of soap. How many packages can you create?
Explain why the solution to this problem is the gcd(792, 400).