### Some answers and variations from questions in Book

From section 2.5 first some examples before the question in the part 2 review:
• Use the Euclidean Algorithm to express d=gcd(a,b) as a linear combination of a and b, i.e. d = sa+tb.
1. 123,2347; remember algorithm in a nutshell: find r_(n-2) = r_(n-1) * q_(n-1) + r_n with 0< r_n < r_(n-1) until r_n is zero, then r_(n-1) is gcd.
Also note that r_n can be expressed as a linear combination of r_(n-2) and r_(n-1)
Simply r_n = r_(n-2) - q_(n-1) * r_(n-1) and keep working backwards.
At a glance, 123 * 20 is larger than 2347, so try 19: 123 * 19 = 2337
Hence 2347 = (19)*123 + 10 (r_2 is 10 and 10=2347 - (19)*123)
123 = (12)*10 + 3 (3=123 - (12)*10)
12 = (4)*3 (much fewer steps than O(log(123)))
Hence gcd(123,2347) is 3. Work backwards with substitutions:
We have 3 = 123 - 12 * 10 = 123 - 12 * (2347 - 19 * 123 )
Just simplify to get 3 = 20 * 123 - 12 * 2347

2. d = gcd(3454,4666). Clearly q_1 is just 1:
4666 = 1 * 3454 + 1212 (hence, for back substitution: 1212 = 4666 - 3454)
3454 = 2 * 1212 + 1030 (so 1030 = 3454 - 2 * 1212)
1212 = 1 * 1030 + 182 (and 182 = 1212 - 1030)
1030 = 5 * 182 + 120 (and 120 = 1030 - 5 * 182)
182 = 1 * 120 + 62 (and 62 = 182 - 120)
120 = 1 * 62 + 58 (and 58 = 120 - 62)
62 = 1 * 58 + 4 ( 4 = 62 - 58)
58 = 14 * 4 + 2 (and finally 2 = 58 - 14 * 4)

So 2 = 58 - 14 * 4 = 58 - 14 ( 62 - 58) = 15 * 58 - 14 * 62 =
15 * (120 - 62 ) - 14 * 62 = 15 * 120 - 29 * 62
15 * 120 - 29 * (182 - 120) = 44 * 120 - 29 * 182 =
44 * (1030 - 5 * 182) = 44 * 1030 - 249 * 182 =
44 * 1030 - 249 * (1212 - 1030) = 293 * 1030 - 249 * 1212
= 293 * (3454 - 2 * 1212) - 249 * 1212 = = 293 * 3454 - 835 * 1212 =
293 * 3454 - 835 * (4666 - 3454) = 1128 * 3454 - 835 * 4666.

• Is there a solution to 3454 * x = 3 (mod 4666)?
No since 3 is not a multiple of gcd(3454,4666).
• Is there a solution to 3454 * x = 4 (mod 4666)?
Yes, since 4 is a multiple of gcd(3454,4666)=2! What's a solution? Well, we know that 2 = 1128 * 3454 - 835 * 4666, hence 4 = 2(1128 * 3454 - 835 * 4666) = 2256 * 3454 - 1670 * 4666.
Therefore 2256 is a solution, since 2256 * 3454 = 4 PLUS a multiple of 4666.
Are there any other solutions mod 4666? Yes, since gcd is not 1 there are more. take 4666/gcd = 2333, hence 2256 + 2333 = 4589 Is another solution. Let's test 3454 * (2256 + 2333) = 3454 * 2256 + 3454 * 23333 which is congruent to 3454 * 2256 (since 3454 * 2333 is a multiple of 4666), and we know that 3454 * 2256 is congruent to 4 by the above.
• Verify that 937 is the inverse of 13 mod 2436.
Not much to do here but just multiply 937 * 13 = 12181 and then compute 12181 mod 2436 = 12181 - [ 12181/2436] * 2436 = 12181 - 5 * 2436 = 12181 - 12180 = 1. Yes it is the inverse.
• The inverse of 4 mod 17.
Could use Euclid: 17 = 4 * 4 + 1 ( hence 1 = 17 - 4 * 4 ). This means that -4 is the inverse, but we prefer to realize that -4 is 13 mod 17. I.e. 4 * 13 = 52 = 3*17 + 1.
Note, we could also notice that the inverse of 2 (mod 17) is obviously 9. Therefore since 4 is 2 squared, the inverse of 4 is the square of the inverse of 2: (2*2)(2^{-1} * 2^{-1}) = 1. So 9 squared is 81. What is this mod 17? Well 4 * 17 = 68, hence 81 is, as expected, 13 more than a multiple of 17.
• Very important question: Show that the inverse of a mod m does not exist if gcd(a,m) > 1.
Indeed, suppose that a does have an inverse mod m, call it y. Then a * y is some multiple of m plus 1. I.e. a*y = 1 + k*m. So a*y - k*m = 1. But if d is the gcd(a,m), then d divides the left hand side, a*y - k*m, so it must divide the r.h.s., i.e. d is 1. Remember, this is just a special case of the fact that a*x=b (mod m) has a solution iff b is a multiple of gcd(a,m).
• Find all x such which give us the code <1,1> in the <mod 2, mod 3> system.
Well x = 1 (mod 2), and x = 1 (mod 3). This means that
(by mod 2) x is one of 1, 3, 5, 7, 9, 11, ... (multiples of 2 plus 1)
and (by mod 3) x is one of 1, 4, 7, 10, 13, ... (multiples of 3 plus 1)
Therefore x is any of 1, 7, 13, ... (i.e. by the Chinese remainder theorem, x is unique mod 2 * 3, i.e. 1, which means that 1 plus any multiple of 6 is a solution).
• Now in the < 5, 7> system work out the sum of 5 and 8.
Well 5 is < 0,5> and 8 is < 3, 1 >. Hence the code of the sum 5 + 8 is < 0 + 3, 5 + 1> = < 3, 6 >. Now we must decode < 3, 6> which means find an x such that
x= 3 (mod 5) and x = 6 (mod 7). As in the previous question we can use just inspection: from mod 5 x is 3 or 8 or 13 or 18 or ...
and mod 7, x is 13 or 20 or ... i.e. 6 plus a multiple of 7.
13 is in the intersection of these sets, hence x = 13 is the solution mod 5 * 7.
The technique from The Chinese remainder theorem is as follows:
Solve M_1 * y_1 = 1 (mod 5), i.e. 7 * y_1 = 1 (mod 5)
and also M_2 * y_2 = 1 (mod 7) i.e. 5 * y_2 = 1 (mod 7)
By inspection we can see that y_1 = -2 = 3 (mod 5) and y_2 = 3 (mod 7).
So x = a_1 ( M_1 * y_1) + a_2 (M_2*y_2) = 3 (7 * 3 ) + 6 (5*3)= 63 + 90 = 153 (mod 5*7) = 153 - 4 * 35 = 153 - 140 = 13.

Some Problems from Section 2.3 P 124:
1. Question 12: How many 0's at the end of 100! ?
Well each 0 corresponds to a power of 10 = 2*5 in the sense that there are k zeroes iff both 2^k and 5^k divide 100! = 100 * 99 * ...
There are 50 even numbers so certainly 2^{50} divides, let's focus on the power for 5.
We've got 5, 10, 15, ... which is 20 powers of 5, and 25, 50, 75, 100 each contribute one extra. So we know 5^{24} divides 100!.
The important thing is to show that now larger power will divide.
This is the same as showing that 5 does not divide
100! / (5^{24}) = 100/25 * 99 * ... * 96 * (95/5) * 94 * ... * (50/25) * ... * 6 * (5/5) * 4 * 3 * 2 * 1
Remember that if gcd(a,b)=1 and a | b*c, then a | c. Let a = 5 and assume that a divides this big product 100!/5^{24}. Go through the numbers one by one, noting that gcd(a,100/25) = gcd(a,99) = ... to deduce the contradiction that a must divide 1. Obviously it does not so the assumption that a divides the product must be incorrect.
A quicker way is to note that 5 is prime and we have the theorem that if a prime divides a product of numbers it must actually divide one of the numbers. Therefore 5 does not divide
100/25 * 99 * ... * 96 * (95/5) * 94 * ... * (50/25) * ... * 6 * (5/5) * 4 * 3 * 2 * 1
2. Question 24: (a) 2^{min(2,5)} * 3^{min(3,3)} * 5^{min(5,2)} = 2^2 * 3^3 * 5^2
(b) 2^1 * 3^1 * 5^0 * 7^0 * 11^1 * 13^0 * 17^0
3. Question 27: (b) compute -97 mod 11 . -9 * 11 is -99 and -97 is -99 + 2, hence -97 = 2 (mod 11).
(c) 155 mod 19 = (155 - 190) mod 19 = (-35) mod 19 = (-35 + 38) mod 19 = 3.
(d) -221 mod 23 = (-221 + 230 ) mod 23 = 9
4. Question 33: Prove that if n|m and a=b (mod m), then a=b (mod n).
Easy, assume a = b (mod m), hence a - b = k*m for some k. Now we have that n|m, hence m = s*n for some s. Then a - b = k*(s*n) = (k*s)*n. This means that a-b is a multiple of n which is equivalent to a = b (mod n).
5. Question 36: If a = b (mod m), then gcd(a,m) = gcd(b,m).
Lots of ways to do this. One is remember in the proof of the Euclidean algorithm: if r = q*s + c, then gcd(r,s) = gcd(s,c).
Apply that here, we know that a = b + q*m for some q (since a=b (mod m)).
Now some from P88.
1. Question 12: x log(x) is O(x^2) but x^2 is not O(x log(x)).
We know that x is O(x) and log(x) is O(x), hence x * log(x) is O(x * x), by the Theorem stating f1 is O(g1) and f2 is O(g2) implies that f1 * f2 is O(g1 * g2).
Directly from the definition we show x^2 is not O(x log(x)) by contradiction.
Assume that there is some C and k so that
|x^2| < C * | x log(x) | for all x > k.
Can assume that k is large enough so that everything is positive so we get
x^2 < C * x * log(x) allowing cancelling (if x> 0)
x< C * log(x) for all x > k. Well we could actually stop here by saying that this would mean that the definition of x is O(log(x)) appears to be satisfied but we've been told to assume that x is not O(log(x)).
2. I forgot to prove in class that x is not O((log x)^2).
Well if x< C * (log x)^2 for all x > k, take logs of both sides:
log(x) < log(C) + 2 log(log(x)) for all x> k.
Take really big x of the form 2^y (for y> k, we get x> k)
log(x) = log(2^y) = y < log(C) + 2 log(log(x)) = log(C) + 2 log(y) for all y> k
But we know y < log(C) + 2 log(y) does not hold for all y> k, for any k and C, since y is not O(log(y)).
3. Question 20: (a) (n^3 + n^2 log n)(log n + 1) + (17 log n + 19)(n^3 + 2)
is O(n^3 log n). If we expand this out we get a sum of terms of the form n^i * (log n)^j. If i < 3, then it doesn't matter what j is we still have a term which is O(n^3). While looking it over we see that if i = 3, then j is never more than 1. So a sum of terms, each of which is O(n^3 log n), is itself O(n^3 log n).
4. Question 41 and 42: Prove that O(n log n) = O(log n!).
We did in class that n! < n^n, hence log n! < log n^n = n log n.
This gives log n! is O(n log n). The other direction is harder.
Note that n! > (n/2)^(n/2) -- For convenience let's assume that n is an even number (otherwise you work with floor(n/2)).
Therefore log n! > log( (n/2)^(n/2) ) = (n/2) log (n/2) = (n/2) log n - (n/2) log 2.
It is easy to see that n log n is O((n/2) log n - (n/2) log 2 ) and the above inequality shows that (n/2) log n - (n/2) log 2 is O(log n!).
Therefore n log n is O(log n!).
Finally some from Page 78
1. Question 4: find a_0,..., a_4 in the cases:
(a) 2^{-n}: a_0 = 1, a_1 = 1/2, a_2 = 1/4, a_3 = 1/8
(b) 3: a_0 = 3, a_1 = 3, a_2 = 3, a_3 = 3
(c) 7+4^n: a_0=8, a_1=11, a_2=23, a_3=71
(d) 2^n + (-2)^n: a_0=2, a_1 = 2+1/2, a_2= 4+1/4, a_3=8+1/8
2. Question 6: Find SIGMA_{j in S} with S={1,3,5,7} for each sequence:
(a) a_j=j: SIGMA_{j in S} j = 1+3+5+7
(b) a_j=j^2: SIGMA_{j in S} j^2 = 1+9+25+49
(c) a_j=1/j: SIGMA_{j in S} 1/j = 1+ 1/3 + 1/5 + 1/7
(d) a_j=1: SIGMA_{j in S} 1 = 1+1+1+1 = 4.
3. Question 11: SIGMA_{j =1 to n} (a_j - a_{j-1})
= (a_2-a_1) + (a_3-a_2) + ... + (a_n - a_{n-1}) So we just cancel terms
leaving the only that do not cancel: a_n - a_1
4. Question 8: Evaluate the sums for j from 0 to 8:
(a) 1+(-1)^j: for j even this is 2, for j odd it is 0. So for j from 0 to 8
2 + 0 + 2 + 0 + 2 + 0 + 2 + 0 + 2 = 10
(b) 3^j- 2^j: SIGMA(3^j-2^j) = SIGMA 3^j - SIGMA2^j =
(3^9-1)/2 - (2^9-1)
(c) 2*3^j+3*2^j: = 2 *SIGMA 3^j + 3 * SIGMA 2^j= 2*(3^9-1)/2 + 3 *(2^9-1).
(d) 2^{j+1} - 2^j: Use question 11.
5. We want a procedure/algorithm which will list all the rational numbers between 0 and 1 (in a sense this is what "countable" means)
As the book suggests let's first think of one that lists all those p/q in reduced form such that p+q = n. Then we do an outer loop which makes n go from 1 to infinity.
Procedure list some(n: an integer)
for q :=1 to n
begin
p:= n-q
if (p< q and gcd(p,q)=1) then PRINT(p/q)
end

Now
Procedure rational list (no input)
n:=1
while n> 0
begin
Call list some(n)
n:= n+1
end