Skip to content

Latest commit

 

History

History
96 lines (66 loc) · 3.07 KB

File metadata and controls

96 lines (66 loc) · 3.07 KB

Exercises 31.2-1


Prove that equations (31.11) and (31.12) imply equation (31.13).

Answer

straightforward

Exercises 31.2-2


Compute the values (d, x, y) that the call EXTENDED-EUCLID(899, 493) returns.

Answer

(29, -6, 11)

Exercises 31.2-3


Prove that for all integers a, k, and n,

gcd(a, n) = gcd(a + kn, n).

Answer

gcd(a+kn,n) = gcd(n, (a+kn) mod n) = gcd(n, a)

Exercises 31.2-4


Rewrite EUCLID in an iterative form that uses only a constant amount of memory (that is, stores only a constant number of integer values).

Answer

implementation

Exercises 31.2-5


If a > b ≥ 0, show that the invocation EUCLID(a, b) makes at most 1 + logφ b recursive calls. Improve this bound to 1 + logφ(b/ gcd(a, b)).

Answer

φ^(k+1) / Root(5) < F(k+1) < b

k + 1 < 1/2logφ 5 + logφ b

k <= logφ b + 1

The second is pretty simple, before executing, we divide gcd(a,b) and get the answer.

Exercises 31.2-6


What does EXTENDED-EUCLID(Fk+1, Fk) return? Prove your answer correct.

Answer

a b 0
2 1 (1,0,1)
3 2 (1,1,-1)
5 3 (1,-1,2)
8 5 (1,2,-3)
13 8 (1,-3,5)

(1,1,2,3,5,8,13,...)

we can conclude that

  • if k is odd, the answer is (1, F_k-2, -F_k-1)
  • if k is even, the answer is (1, -F_k-2, F_k-1)

If k is odd,

Fk+1 * Fk-2 - Fk * Fk-1 = Fk * Fk-2 + Fk-1 * Fk-2 - Fk * Fk-1 = Fk-1Fk-2 + Fk-2Fk-2 + Fk-1Fk-2 - Fk-1Fk-1 - Fk-1Fk-2 = Fk-2Fk-2 + Fk-1Fk-2 - Fk-1Fk-1 = 1(by mathematical induction we can obtain the result)

if k is even, the prove is the same.

Exercises 31.2-7


Define the gcd function for more than two arguments by the recursive equation gcd(a0, a1, ..., an) = gcd(a0, gcd(a1, a2, ..., an)). Show that the gcd function returns the same answer independent of the order in which its arguments are specified. Also show how to find integers x0, x1, ..., xn such that gcd(a0, a1, ..., an) = a0x0 + a1x1 + ··· + anxn. Show that the number of divisions performed by your algorithm is O(n + lg(max {a0, a1, ..., an})).

Answer

UNSOLVED

Exercises 31.2-8


Define the gcd function for more than two arguments by the recursive equation gcd(a0, a1, ..., an) = gcd(a0, gcd(a1, a2, ..., an)). Show that the gcd function returns the same answer independent of the order in which its arguments are specified. Also show how to find integers x0, x1, ..., xn such that gcd(a0, a1, ..., an) = a0x0 + a1x1 + ··· + anxn. Show that the number of divisions performed by your algorithm is O(n + lg(max {a0, a1, ..., an})).

Answer

implementation

Exercises 31.2-9


Prove that n1, n2, n3, and n4 are pairwise relatively prime if and only if

gcd(n1n2, n3n4) = gcd(n1n3, n2n4) = 1.

Show more generally that n1, n2, ..., nk are pairwise relatively prime if and only if a set of ⌈lg k⌉ pairs of numbers derived from the ni are relatively prime.

Answer

UNSOLVED


Follow @louis1992 on github to help finish this task