Prove that equations (31.11) and (31.12) imply equation (31.13).
straightforward
Compute the values (d, x, y) that the call EXTENDED-EUCLID(899, 493) returns.
(29, -6, 11)
Prove that for all integers a, k, and n,
gcd(a, n) = gcd(a + kn, n).
gcd(a+kn,n) = gcd(n, (a+kn) mod n) = gcd(n, a)
Rewrite EUCLID in an iterative form that uses only a constant amount of memory (that is, stores only a constant number of integer values).
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)).
φ^(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.
What does EXTENDED-EUCLID(Fk+1, Fk) return? Prove your answer correct.
| 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.
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})).
UNSOLVED
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})).
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.
UNSOLVED
Follow @louis1992 on github to help finish this task.