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.
a) k=4 case =>) Trivial. <=) can be proved by proof by contraposition . Assume n1, n2, n3, and n4 are not pairwise relatively prime, then there exists a pair i, j (1 <=i < j <= 4) such that gcd(ni, nj) > 1. If (i, j) = (1, 3), (1, 4), (2, 3), or (2, 4), then gcd(n1n2, n3n4) > 1. If (i, j) = (1, 2) or (3, 4), then gcd(n1n3, n2n4) > 1. Therefore, at least one of pair of gcd must be greater than 1.
b) General case Assume the given integers are n0, ..., n(k-1). (The indices are changed.) Then, we can construct ⌈lg k⌉ pairs {(xt, yt)} where xt is the product of { nj | t-th bit of j is 0 } and yt is the product of { nj | t-th bit of j is 1 }.
For example, with the following k=4 case,we get (x1, y1) = (n0n2, n1n3), (x2, y2) = (n0n1, n2n3). 0 : 00 1 : 01 2 : 10 3 : 11
Proof : =>) Any prime p is a divisor of at most one of {nj}, so p is also a divisor of at most one of xi and yi for each i. <=) can be proved by proof by contraposition proof by contraposition. Assume n0, n1, …, n(k-1) are not pairwise relatively prime, then there exists a pair i, j (0 <= i < j < k) such that gcd(ni, nj) = r > 1. Because i and j are different and less than k, there exists t (<= ⌈lg k⌉) such that the t-th bits of i and j are different. Therefore, we can get gcd(xt, yt) >= gcd(ni, nj) = r > 1.
Follow @louis1992 on github to help finish this task