Mission 1 - Mission 2 - Mission 3 - Mission 4 - Mission 5 - Mission 6 - Mission 7 - Mission 8 - Mission 9 Introductory Number Theory PDF

Preview

Summary

Mission 1 - Mission 2 - Mission 3 - Mission 4 - Mission 5 - Mission 6 - Mission 7 - Mission 8 - Mission 9 merged files: math307mission1s2015.pdf - math307mission2s2015.pdf - math307mission3s2015.pdf - math307mission4s2015.pdf - math307mission5s2015.pdf - math307mission6s2015.pdf - math307mission7s20...

Description

Math 307

Mission 1

Copying answers and steps is strictly forbidden. Evidence of copying results in zero for copied and copier. Working together is encouraged, share ideas not calculations. Explain your steps. This sheet must be printed and attached to your assignment as a cover sheet. The calculations and answers should be written neatly on one-side of paper which is attached and neatly stapled in the upper left corner. Box your answers where appropriate. Please do not fold. Thanks! Problem 1 Your signature below indicates you have: (a.) I read pages 1-42 of Stillwell’s Elements of Number Theory:

.

Problem 2 Use Fibonacci’s algorithm to find an Egyptian representation of 5/43. Show your work. Problem 3 exercise 1.2.2 on page 5. Problem 4 Wildstyle works at an awesome coffee shop sells discount coffee in two sizes: Jabba and Throatwoblermangrove. She sells Jabba for 31 dollars each and Throatwoblermangrove for 28 dollars each. If her total revenue from a day is 1460 dollars, how many of each size coffee might she manufacture in a day? Problem 5 exercise 1.4.2 on page 8. Problem 6 exercise 1.5.1 on page 11. Problem 7 exercise 1.5.3 on page 11. Problem 8 exercise 1.5.4 on page 11. Problem 9 Show that x such that x2 + (161)2 = (289)2 is divisible by 60. Problem 10 Find the continued fraction of 5/43. I probably shouldn’t tell you this, but, See page 96 of this free legal pdf by Stein no joke Problem 11 exercise 2.3.1 on page 28. You might use Sage to check your answer as shown on page 33 of this free legal pdf by Stein no joke Problem 12 exercise 2.5.1 on page 32. Problem 13 exercise 2.5.7 on page 33. Problem 14 exercise 2.6.2 and 2.6.3 on page 35 Problem 15 exercise 2.6.4 on page 35 Problem 16 extend the map one more step beyond what is pictured on page 38. Problem 17 Let m, a, b ∈ Z such that m 6= 0. Prove: a|b iff ma|mb. Problem 18 Let a, d ∈ Z. Prove: if d|a then |d| ≤ |a|.

Problem 19 Suppose a, b, c ∈ Z and a, b, c ≥ 0. Prove or disprove the claim below: If a|(b + c) then a|b and a|c. Problem 20 Prove the square of every odd integer is of the form 8k + 1 for some k ∈ Z.

Math 307

Mission 2

Same instructions as Mission 1. Thanks! Problem 21 Your signature below indicates you have: (a.) I read pages 43-65 of Stillwell’s Elements of Number Theory: (b.) I read Cook’s handout on Modular Arithmetic:

. .

Problem 22 Let a, b, c ∈ Z. Prove: if a|b and b|c then a|c. Problem 23 Let a, b, c ∈ Z. Prove: if a|b and c|d then ab|cd. Problem 24 Convert (89156)10 to base 8 notation. Problem 25 exercise 3.1.4 on page 45 Problem 26 exercise 3.2.1 on page 48 Problem 27 exercise 3.3.4 on page 51 Problem 28 exercise 3.4.3 on page 53 Problem 29 Define f (x) = 3x + 2 where x ∈ Z4 and f (x) ∈ Z5 . Is f so defined a function ? Problem 30 Write the addition and multiplication tables for Z4 = {0, 1, 2, 3}. Problem 31 Explain why H = {1, 2, 3} does not form a group with respect to multiplication mod 4. Problem 32 For which a ∈ Z is it the case that 4a + 3 = 6 in Z12 ? Problem 33 Find the remainder of 510 divided by 19. Problem 34 Find the final hexidecimal digit of 1! + 2! + 3! + 4! + 5! + 6! + · · · + 1000!. Useful reminder: Recall a hexidecimal number is a base 16 representation n = ao + a1 (16)+ a2 (16)2 +· · ·+ ak (16)k where the hexidecimal digits a0 , a1 , . . . , ak ∈ {0, 1, . . . , 15}. However, we use notation 10 = A, 11 = B, 12 = C, 13 = D, 14 = E and 15 = F to write such numbers. For example, AF = 10(16) + 15 = 175. To be more pedantic, (AF )16 = (175)10 . Problem 35 How many zeros are there at the end of 200! in decimal notation? Problem 36 Show that the greatest common divisor of two even integers is even. 15n+4 Problem 37 Prove or disprove: for any positive integer n the fraction 10n+3 is in lowest terms. For 3 1 3 example, 6 is not in lowest terms as 6 = 2 . A fraction in lowest terms cannot be further reduced as a single fraction. (of course, with egyptian fractions and continued fractions we have many other options, but that is beside the point here)

Problem 38 Prove by induction on k: If p is prime and p|a1 a2 . . . ak then p|ai for at least one ai . √ Problem 39 Show that 3 5 is irrational. Hint 13 = 1 and 23 = 8. √ Problem 40 Show that if a positive integer m is not a perfect square, then m is irrational.

Math 307

Mission 3

Same instructions as Mission 1. Thanks! Problem 41 Your signature below indicates you have: (a.) I read pages 66-75 of Stillwell’s Elements of Number Theory: (b.) I read Cook’s handout on Basic Algebra in Zn :

. .

Problem 42 exercise 3.3.3 page 51 Problem 43 exercise 3.5.1 and 3.5.2 page 55 Problem 44 An ancient method to find primes is known as the sieve Eratosthenes. See this wikipedia article for example. Verify the list of primes shown on the wikipedia article and find the smallest integer n such that [1000000, n] has 7 primes via experimenting with the prime-finding command in Sage. √ Problem 45 By this time we ought to have shown that any prime divisor of n is at most n. Use this insight and other math we have discussed to prove or disprove that 203 is prime. Problem 46 exercise 3.6.4 page 57 Problem 47 exercise 3.7.1 and 3.72 page 59. Problem 48 exercise 3.7.3 page 59 Problem 49 exercise 3.8.3 page 61 Problem 50 find the least positive residue of 3100000 modulo 35. Use Euler’s Theorem. Problem 51 exercise 4.1.2 page 70 Problem 52 exercise 4.3.1 page 72 Problem 53 exercise 4.4.1 page 73 Problem 54 I chose m, b ∈ Z26 to make the affine shift cipher f (x) = mx + b based on the alphabet code A = 0, B = 1, · · · Z = 25. You are given that the message ”CAT” is encrypted to ”KEJ”. Find m and b and decode the message ”REDMJU”. Problem 55 Prove that a(a + 1)(2a + 1) is divisible by 6 for every integer a. Problem 56 Show that f (x) = x5 − x2 + x − 3 has no integer roots by showing f (x) ≡ 0 (mod 4). It is convenient for this sort of problem to use the least absolute residues: Z4 = {−1, 0, 1, 2} as they permit faster calculation of f (x). Problem 57 Decide if 3x ≡ 5 (mod 7) or 12x ≡ 15 (mod 22) has solutions. Find the solutions for the congruence which has solutions. Problem 58 Simultaneously solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7). Notice, you can use the Sage to check your answer here. See page 30 of this free legal pdf by Stein no joke

Problem 59 Find the solutions of f (x) = x3 + 4x2 + 19x + 1 ≡ 0 (mod 52 ) Problem 60 Find all the roots of x18 + 4x14 + 3x + 10 ≡ 0 (mod 21)

Math 307

Mission 4

Same instructions as Mission 1. Thanks! Problem 61 Your signature below indicates you have: (a.) I read pages 76-100 of Stillwell’s Elements of Number Theory:

.

Problem 62 exercise 5.1.1 page 78 Problem 63 exercise 5.1.2 page 78 Problem 64 exercise 5.1.3 page 78 Problem 65 exercise 5.1.4 page 78 Problem 66 exercise 5.2.1 page 79 Problem 67 exercise 5.2.2 page 79 Problem 68 exercise 5.3.2 page 81 Problem 69 exercise 5.3.3 page 81 Problem 70 exercise 5.4.1 page 83 Problem 71 exercise 5.4.2 page 83 Problem 72 exercise 5.4.3 page 83 Problem 73 exercise 5.4.4 page 83 Problem 74 exercise 5.4.5 page 83 Problem 75 exercise 5.6.1 page 90 Problem 76 exercise 5.6.2 page 90 Problem 77 exercise 5.6.3 page 90 Problem 78 apply the pigeonhole principle to a class which has 41 students attending but just 40 seats. Problem 79 an infinite number of cochroaches infest an apartment building with 42 apartments. Apply the pigeonhole principle to make a disturbing statement about the folks who leave food out. Problem 80 and now for a bit of nostalgia: what is the remainder of 2432 divided by 7 ?

Math 307

Mission 5

Same instructions as Mission 1. Thanks! Problem 81 Your signature below indicates you have: (a.) I read pages 101-116 of Stillwell’s Elements of Number Theory: Problem 82 exercise 6.1.1 page 103 Problem 83 exercise 6.1.2 page 103 Problem 84 exercise 6.1.3 page 103 Problem 85 exercise 6.1.4 page 103 Problem 86 exercise 6.2.1 page 104 Problem 87 exercise 6.2.2 page 104 Problem 88 exercise 6.2.4 page 104 Problem 89 exercise 6.3.4 page 106 Problem 90 exercise 6.3.5 page 106 Problem 91 exercise 6.3.6 page 106 Problem 92 exercise 6.4.3 page 108 Problem 93 exercise 6.4.4 page 108 Problem 94 exercise 6.5.1 page 110 Problem 95 exercise 6.5.2 page 110 Problem 96 exercise 6.5.3 page 110 Problem 97 exercise 6.5.4 page 110 Problem 98 exercise 6.5.5 and 6.5.6 page 110 Problem 99 exercise 6.6.1 page 112 Problem 100 exercise 6.6.3 page 112

.

Math 307

Mission 6

Same instructions as Mission 1. Thanks! Problem 101 Your signature below indicates you have: (a.) I read pages 117-137 of Stillwell’s Elements of Number Theory: Problem 102 exercise 7.1.1 page 119 Problem 103 exercise 7.1.2 page 119 Problem 104 exercise 7.1.3 page 119 (skip it if you get stuck here) Problem 105 exercise 7.2.1 page 120 Problem 106 exercise 7.2.2 page 120 Problem 107 exercise 7.2.3 page 121 Problem 108 exercise 7.2.4 page 121 Problem 109 exercise 7.3.1 page 122 Problem 110 exercise 7.3.2 page 122 Problem 111 exercise 7.3.3 page 122 Problem 112 exercise 7.3.4 page 122 Problem 113 exercise 7.3.5 page 122 Problem 114 exercise 7.3.6 page 122 Problem 115 exercise 7.3.7 page 122 Problem 116 exercise 7.4.1 page 126 Problem 117 exercise 7.4.2 page 126 Problem 118 nostalgia: Prove that if a is relatively prime to 72 then a12 ≡ 1 (mod 72). Problem 119 nostalgia: Find the remainder of 20! when divided by 23. Problem 120 nostalgia: Prove or disprove that 674, 310, 976, 375 is divisible by 11.

.

Math 307

Mission 7

Same instructions as Mission 1. Thanks! Problem 121 Your signature below indicates you have: (a.) I read pages 138-157 of Stillwell’s Elements of Number Theory:

.

Problem 122 exercise 8.1.1 page 141 Problem 123 exercise 8.1.2 page 141 Problem 124 exercise 8.2.1 page 143 Problem 125 exercise 8.2.3 page 143 Problem 126 exercise 8.2.4 page 143 Problem 127 exercise 8.3.1 page 145 Problem 128 exercise 8.3.2 page 145 Problem 129 exercise 8.3.3 page 145 Problem 130 exercise 8.3.4 page 145 Problem 131 exercise 8.3.5 page 145 Problem 132 exercise 8.4.2 page 147 (this would seem to be a descent question) Problem 133 exercise 8.5.1 page 148 Problem 134 exercise 8.6.1 page 151 Problem 135 exercise 8.6.3 page 151 Problem 136 exercise 8.6.4 page 151 Problem 137 exercise 8.8.3 page 153 Problem 138 nostalgia: Let a ∈ Z. Show that a12 − 1 is divisible by 35 whenever gcd(a, 35) = 1 Problem 139 nostalgia: What is the remainder of 4232 when divided by 7 Problem 140 nostalgia: Suppose 2x99561 = [3(523+x)]2 where x is a missing digit (base ten is assumed). Find all possible values of x.

Math 307

Mission 8

Same instructions as Mission 1. Thanks! Problem 141 Your signature below indicates you have: (a.) I read pages 158-195 of Stillwell’s Elements of Number Theory: Problem 142 exercise 9.1.1 page 161 Problem 143 exercise 9.1.2 page 161 Problem 144 exercise 9.1.3 page 161 Problem 145 exercise 9.1.4 page 161 Problem 146 exercise 9.1.5 page 161 Problem 147 exercise 9.1.6 page 161 Problem 148 exercise 9.2.1 page 164 Problem 149 exercise 9.2.2 page 164 Problem 150 exercise 9.4.1 page 169 Problem 151 exercise 9.5.1 page 171 Problem 152 exercise 9.5.2 page 171 Problem 153 exercise 9.8.2 page 178 Problem 154 exercise 10.2.1 page 185 Problem 155 exercise 10.2.2 page 185 Problem 156 exercise 10.2.3 page 185 Problem 157 exercise 10.2.4 page 185 Problem 158 exercise 10.2.5 page 185 Problem 159 exercise 10.3.1 page 188 Problem 160 exercise 10.3.2 page 188

.

Math 307

Mission 9

Same instructions as Mission 1. Thanks! Problem 161 Your signature below indicates you have: (a.) I read pages 196-220 of Stillwell’s Elements of Number Theory: Problem 162 exercise 10.4.1 page 191 Problem 163 exercise 10.4.2 page 191 Problem 164 exercise 10.4.3 page 191 Problem 165 exercise 10.5.1 page 193 Problem 166 exercise 10.5.2 page 193 Problem 167 exercise 10.5.3 page 193 Problem 168 exercise 11.1.1 page 199 Problem 169 exercise 11.2.1 page 201 Problem 170 exercise 11.3.1 page 202 Problem 171 exercise 11.3.2 page 202 Problem 172 exercise 11.3.3 page 202 Problem 173 exercise 11.3.4 page 202 Problem 174 exercise 11.3.5 page 202 Problem 175 exercise 11.4.1 page 206 Problem 176 exercise 11.4.2 page 206 Problem 177 exercise 11.4.3 page 206 Problem 178 exercise 11.4.4 page 206 Problem 179 exercise 11.4.5 page 206 Problem 180 exercise 11.4.6 page 206

....