Problem list

I will only do the ones that I didn't assign as forum problems. If you disagree with my answers, email me and check because I could have a typo.

WORKSHEET I : SEQUENCES AND SETS OF OBJECTS

(1) = (h), (2) = (m), (4) = (i), (5) = (e), (7)=(p),

(8) = (d), (9) = (f), (10) = (j), (11) = (b), (12) = (n),

(13) = (a), (14) = (c), (15)=(o), (17) = (g), (18) = (k), (19)= (l)

(3) either a widget of size n or a doodle of size m

(6) a widget of size less than or equal to n

(16) a pair consisting of an integer between 1 and n and a widget of size n

SEQUENCES AND SETS OF OBJECTS II, first part

(1) a_0 + a_1 + ... + a_n + b_0 + b_1 + ... + b_n

(2) a_0 b_0 + a_1 b_2 + a_2 b_4 + ... + a_n b_{2n}

(3) a_0 + b_1 + a_2 + b_3 + a_4 + b_5 + ... + a_{n-1} + b_n (if n is odd)

a_0 + b_1 + a_2 + b_3 + a_4 + b_5 + ... + b_{n-1} + a_n (if n is even)

(4) a_n (b_0 + b_1 + ... + b_{n-1})

(5) (a_0+a_1) b_0 + (a_2+a_3) (b_0 + b_1) + (a_4+a_5)(b_0 + b_1 + b_2) + ... + (a_{n-1} + a_n) (b_0 + b_1 + ... + b_{(n-1)/2}) (if n odd)

(a_0+a_1) b_0 + (a_2+a_3) (b_0 + b_1) + (a_4+a_5)(b_0 + b_1 + b_2) + ... + (a_{n-2} + a_{n-1}) (b_0 + b_1 + ... + b_{n/2-1}) + a_n (b_0 + b_1 + ... + b_{n/2}) (if n is even)

(6) a_1 + a_2 + ... + a_n

(7) n a_0 + (n-1) a_1 + ... + a_{n-1}

(8) a_1 + 2 a_2 + 3 a_3 + ... + n a_n

(9) a_n (b_0 + b_1 + ... + b_n)

(10) (by in between I mean "inclusive," if you interpreted in between to mean strictly "not including the integer and not including n" then you will get a different answer) n a_1 + (n-1) a_2 + (n-2) a_3 + ... + 2 a_{n-1} + a_n

(11) there is a bit of a typo there. Remove the words "a pair consiting of" and then the problem makes a little more sense. in this case the answer is a_2 + 2 a_3 + 3 a_4 + ... + (n-1) a_n

(12) a_n (a_n-1) b_n

(13) C(a_n,3)

Drill and Skill number theory problems

I am just giving hints on these.

first: (a) your answer should be a prime number and (b) for both these use the euclidean algorithm

second: 17529^2 - 277^2 = (17529 + 277)(17529 - 277) = 0 (mod 69689) so we have two factors that themselves are smaller than 69689 and 69689 divides their product. Take the gcd of 69689 and either one of these factors and you will find a common factor.

third: 54 = -25 = - 5^2 (mod 79) so you are really computing (-5)^80 (mod 79). Now use Fermat's little theorem.

fourth: (a) (15/29) = (5/29)(3/29) and use quadratic reciprocity to flip each of these. (b) since 29 is prime the Legendre symbol (15/29) tells you if there exists a solution to x^2 = 15 (mod 29) or not. If the Legendre symbol is 1 then there is an x, if the Legendre symbol is -1 then there is no such x.

fifth: 30^2445 = 30^((4891-1)/2) = 30^21 (mod 4891) this one takes a lot of computation but I got 2679 which is obviously not equal to the Jacobi symbol. If 4891 was prime then J(30,4891) = (30/4891) = 30^((4891-1)/2) (mod 4891). Since this is not the case this tells us that 4891 is not prime.

sixth: 22 = 2^7. Solve 2^(7 S_A) = 19 = 2^37 (mod 53) and 2^(7 S_B) = 37 = 2^30 (mod 53). Then figure out what 2^(7 S_A S_B) is equal to.

seventh: use the euclidean algorithm to figure out gcd(11,336*210) = gcd(11,70560) and the d and s such that d*11 + s*70560 = 1.

eighth: 3^70565 = 3^(70560 + 5) = 3^5 (mod 71107)

Back to the web page for Math 5020.