English

not defined

no text concepts found

Worksheet 1 - Going round in circles Most of these questions were taken from: http://nrich.maths.org/308 , http://nrich.maths.org/6651 and http://nrich.maths.org/content/id/6651/Going%20Round%20In%20Circles.pdf. Charlie said: "It's Sunday today, so it will be Sunday again in 7 days.. and in 770 days... and in 140 days... and in 35035 days... and in 14000000007 days!" Alison said: "and it will be Tuesday in 2 days... and in 72 days... and in 702 days... and in 779 days... and in 14777002 days!" 1) Do you agree with all of Charlie's and Alison's statements? 2) Charlie and Alison chose numbers that were easy to work with. Can you see why they were chosen? 3) If today is Sunday, what day will it be in 15 days? 26 days? 234 days? 1000? 4) If your birthday fell on a Sunday this year, what day will it fall on next year? 5) If it is autumn now, what season will it be in 100 seasons? 6) If it is 9 am now, what time will it be in 50 hours? 7) If it is November, what month will it be in 1000 months? 8) If it is midday now, will it be light or dark in 539 hours? Worksheet 1 - Going round in circles 1 You don't have to finish these questions. 9) A railway line has 27 stations on a circular loop. If I fall asleep and travel through 312 stations, where will I end up in relation to where I started? 10) If a running track is 400 metres around, where will I be in relation to the start after running 6 miles (approximately 9656 metres)? 11) I was facing North and then spun around through 945° clockwise. In what direction was I facing at the end? 12) If I get on at the bottom of a fairground wheel and the wheel turns through 5000°, whereabouts on the wheel will I be? Worksheet 1 - Going round in circles 2 Worksheet 2 Remainders and congruences Instead of 13 = 1, in modular arithmetic we write 13 ≡ 1 (mod 12) and read it “13 is congruent to 1 modulo 12” or, to abbreviate, “13 is 1 modulo 12”. Examples: 12 ≡ 0 (mod 12) 37 ≡ 1 (mod 12) 17 ≡ 5 (mod 12) -1 ≡ 11 (mod 12) In general: a ≡ b (mod n) if a-b is a multiple of n. Equivalently: a ≡ b (mod n) if a and b have the same remainder when divided by n (remainder modulo n). When we work modulo n we replace all the numbers by their remainders modulo n, that is: 0, 1, 2, …, n-1. 1) Find the remainders modulo 3 of: a) 31 b) 44 c) 75 d) 751 2) Find the remainders modulo 2 of: a) 34 – 15 b) 141 – 78 c) 519 – 444 + 37 Worksheet 2 - Remainders and congruences 1 3) Find the remainders modulo 12 of: a) 31 + 28 + 31 + 30 b) 38 x 4 + 360 c) 66 + 5 + 26 4) Which of the following congruences are true? a) 177 ≡ 17 (mod 2) b) 1322 ≡ 5294 (mod 12) c) 16 + 30 ≡ 2 (mod 2) d) 16 + 30 ≡ 2 (mod 3) You don't have to finish these questions. 5) Which of the following congruences are true? a) 16 + 30 ≡ 2 (mod 12) b) 67 x 73 ≡ 0 (mod 3) c) 14 x 15 x 16 ≡ 6 (mod 3) Worksheet 2 - Remainders and congruences 2 Worksheet 3 Addition and multiplication tables You may use calculators Remember that when we work modulo n we replace all the numbers by their remainders modulo n: 0, 1, 2, …, n-1. So, for example, in the Modulo 4 table you cannot have 4. Modulo 4 addition table: + 0 1 2 3 0 1 2 3 Modulo 4 multiplication table: x 0 1 2 3 0 Worksheet 3 - Addition and multiplication tables 1 2 3 1 You will need these tables later. Modulo 7 addition table: + 0 1 2 3 4 5 6 0 1 2 3 4 5 6 4 5 6 Modulo 7 multiplication table: x 0 1 2 3 4 5 6 0 1 Worksheet 3 - Addition and multiplication tables 2 3 2 You don't have to finish these tables. Modulo 5 addition table: + 0 1 2 3 4 0 1 2 3 4 Modulo 5 multiplication table: x 0 1 2 3 4 0 1 Worksheet 3 - Addition and multiplication tables 2 3 4 3 You don't have to finish these tables. Modulo 6 addition table: + 0 1 2 3 4 5 0 1 2 3 4 5 4 5 Modulo 6 multiplication table: x 0 1 2 3 4 5 0 1 Worksheet 3 - Addition and multiplication tables 2 3 4 Worksheet 4 Divisibility These questions are based or taken from United Kingdom Mathematics Trust (UKMT) Mathematical Challenges. Remember: • N is divisible by 9 if and only if the sum of its digits is divisible by 9. • N is divisible by 3 if and only if the sum of its digits is divisible by 3. • N is divisible by 11 if and only if the alternate sum of its digits is divisible by 11. Start from the right making the units digit positive. 1) Which of these numbers is not a multiple of 3? A 87 B 765 C 6543 D 43210 2) The number 1d3456 is a multiple of 9. Which digit is represented by d? 3) The number 1234d6 is a multiple of 11. Which digit is represented by d? You don't have to finish these questions. 4) The first and fourth digits of the number d63d2 are the same and the number d63d2 is a multiple of 9. Which digit is represented by d? 5) A four-digit number was written on a piece of paper. The last two digits were then blotted out (as shown). If the complete number is exactly divisible by three, by four, and by five, what is the sum of the two missing digits? 8 Worksheet 4 - Divisibility 6 1 You don't have to finish these questions (these are hard ones). 6) Based on the following table of the remainders of the powers of 10: mod 1010 109 108 107 106 105 104 103 102 101 100 2 0 0 0 0 0 0 0 0 0 0 1 3 1 1 1 1 1 1 1 1 1 1 1 4 0 0 0 0 0 0 0 0 0 2 1 5 0 0 0 0 0 0 0 0 0 0 1 6 4 4 4 4 4 4 4 4 4 4 1 7 4 6 2 3 1 5 4 6 2 3 1 8 0 0 0 0 0 0 0 0 4 2 1 9 1 1 1 1 1 1 1 1 1 1 1 10 0 0 0 0 0 0 0 0 0 0 1 11 1 -1 1 -1 1 -1 1 -1 1 -1 1 12 4 4 4 4 4 4 4 4 4 10 1 a) Could you explain why looking at the last digit is enough for the divisibility criteria by 2, 5 and 10? b) Could you give a rule to find the remainders modulo 4? c) Could you give a rule to find the remainders modulo 6? 7) From 1,001=7x11x13 we can conclude that: 1,000 ≡ –1 (mod 7) 1,000 ≡ –1 (mod 11) 1,000 ≡ –1 (mod 13) Therefore we have the following table of remainders of the powers of 1,000: mod 1015 1012 7 -1 1 11 -1 1 13 -1 1 109 -1 -1 -1 106 1 1 1 103 -1 -1 -1 100 1 1 1 Based on that table could you give divisibility criteria by 7, 11 and 13 that work for numbers greater than 1,000? Worksheet 4 - Divisibility 2 Worksheet 5 Powers You are not allowed to use calculators in this section. Example: 9 5 1 …2 , 2 , 2 2 12 8 …2 , 2 , 2 4 2 10 4 2, 2, 2 … 3 6 6 7 11 8 2, 2, 2 … 1) What is the last digit of: a) 123453 b) 25013 c) 451 Worksheet 5 - Powers 1 2) What is the last digit of: a) 957 b) 972 c) 3210 d) 2360 3) What is the remainder when dividing… a) …1080 by 9? b) …69770 by 5? c) …584320 by 4? d) …493184 by 4930? Worksheet 5 - Powers 2 4) Given that the modulo 10 multiplication table is: x 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 8 9 2 0 2 4 6 8 0 2 4 6 8 3 0 3 6 9 2 5 8 1 4 7 4 0 4 8 2 6 0 4 8 2 6 5 0 5 0 5 0 5 0 5 0 5 6 0 6 2 8 4 0 6 2 8 4 7 0 7 4 1 8 5 2 9 6 3 8 0 8 6 4 2 0 8 6 4 2 9 0 9 8 7 6 5 4 3 2 1 Can you determine whether the following are square numbers? a) 6312 b) 4553 c) 9538 d) 1156 e) 1256 You don't have to finish these questions. 5) What is the remainder when dividing 51001 by 6? Hint: 5 ≡ –1 (mod 6). 6) What is the remainder when dividing 212035981234808093146372789686129386749 by 3? 7) Invent a problem like “What is the remainder when dividing ab by c?” where b is a big number. Worksheet 5 - Powers 3 Worksheet 6 Day of the week Month codes Month January February March April May June July August September October November December Number 6 2 2 5 0 3 5 1 4 6 2 4 Mnemonic WINTER has 6 letters February is 2nd month March 2 the beat. APRIL has 5 letters MAY-0 Jun (Jun has 3 letters) The SHARD (5) opened on July 5 August begins with A, the first letterTERM (4 letters) at school First SIX or treat! 11th month (11 => II or 1+1=2) LAST (or XMAS) has 4 letters One way to remember this would be to memorize the following “phone number” 622-503-514-624 or you can memorize one of these tables (or both): Jan Apr Jul Oct 6 5 5 6 Feb May Aug Nov 2 0 1 2 Mar Jun Sep Dec 2 3 4 4 May Aug Feb, Mar, Nov Jun Sep, Dec Apr, Jul Jan, Oct 0 1 2 3 4 5 6 Exception: in a leap year the January code is 5 and the February code is 1 (both one less than in non-leap years). Leap years: You need to remember that leap years (usually) are the years that are multiples of 4. This should be enough most of the time. It can help to know that the Olympic Games and the US presidential elections are held only on leap years. The non-leap years that are multiple of 4 are the years that are multiples of 100 and are not multiples of 400. Examples: 1600 leap, 1700 not leap, 1800 not leap, 1900 not leap 2000 leap, 2100 not leap, 2200 not leap, 2300 not leap 2400 leap Worksheet 6 - Day of the week 1 Year codes We need to remember the years with code 0 (you can change the historical events with some family events): 20th century years with code 0: 1905 Albert Einstein’s annus mirabilis 1911, 22, 33, 44 (first four multiples of 11) 1916 16 = 42 1939 World War II started 1950 Maracanazo (Brazil ’50 World Cup) 1961 Berlin Wall started 1967 The year after England won the World Cup 1972 Munich ’72 Olympics 1978 Argentina ’78 World Cup 1989 Berlin Wall ended 1995 Netscape IPO (beginning of internet boom) 21st century years with code 0: 2000 2006 2017 2023 Year codes in Excel: Worksheet 6 - Day of the week 2 Weekday codes We will use the modulo 7 addition table: Sunday Monday Tuesday Wednesday Thursday Friday Saturday + 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 2 3 4 5 6 0 2 2 3 4 5 6 0 1 3 3 4 5 6 0 1 2 4 4 5 6 0 1 2 3 5 5 6 0 1 2 3 4 6 6 0 1 2 3 4 5 Remember: Weekday code = code of the year + code of the month + date (mod 7) Example You ask: What year were you born? Answer: 1971 How do you find the 1971 code? Remember that 1967, the year after England won the World Cup, has code 0. 1971 code ≡ 71-67 + number of leap years in 1968-1971 (mod 7) 1971 code ≡ 4 + 1 (mod 7) (only 1968 was a leap year in 1968-1971) 1971 code = 5 You ask: What month were you born? Answer: December You remember 624 (the last three digits of 622-503-514-624) December code = 4 (a) You could do 5+4=9 and 9 ≡ 2 (mod 7) and just remember 2. You ask: What day were you born? Answer: 25 Then you compute 5+4+25=34 and 34 ≡ 6 (mod 7). So the day of the week code is 6 which means Saturday. (a) Compute 2+25=27 and 27 ≡ 6 (mod 7) which means Saturday. References: -Arthur Benjamin and Michael Shermer, Secrets of Mental Math. -http://plus.maths.org/content/what-day-week-were-you-born . -A similar method is in http://gmmentalgym.blogspot.com/2011/03/day-of-week-forany-date-revised.html Worksheet 6 - Day of the week 3 1) What are the weekdays of: a) 23/Apr/1999 b) 14/May/1989 c) 1/Jan/1999 d) 1/Jan/2000 e) 3/Feb/1999 f) 3/Feb/2000 Worksheet 6 - Day of the week 4 Acknowledgements and more things to look at I would like to thank Samantha Durbin and Diane Crann from the Royal Institution for all their suggestions that allowed me to improve this presentation. I would like to thank Jim Bumgardner for providing me the video “60 points going around a circle”. On his website http://whitneymusicbox.org you can see other similar videos. A description of his Whitney Music Box is in http://krazydad.com/pubs/whitney_paper.pdf. The videos are based on John Whitney’s visual idea of “incremental drift”. Other related videos are: -Incremental Drift on the Riemann Sphere: http://vimeo.com/2063601 -Incremental TransTower: http://vimeo.com/20824416 or http://vimeo.com/channels/kineticartprojects/20824416 I also would like to thank Charlie Gilderdale and Alison Kiddle from NRICH for their help and in general to NRICH for all the activities on their website. Here is a list of NRICH activities related to Modular Arithmetic: -Shifting Times Tables: http://nrich.maths.org/6713 -Days and Dates: http://nrich.maths.org/308 -Going Round in Circles: http://nrich.maths.org/6651 -GOT IT: http://nrich.maths.org/1272 -What Numbers Can We Make? http://nrich.maths.org/7405 -What Numbers Can We Make Now? http://nrich.maths.org/8280 -Remainders: http://nrich.maths.org/1783 -A Little Light Thinking: http://nrich.maths.org/7016 -The Remainders Game: http://nrich.maths.org/6402 -Charlie's Delightful Machine: http://nrich.maths.org/7024 Finally, if you want to learn more about modular arithmetic you could watch on YouTube the modular arithmetic videos posted by “TheMathsters”. Please feel free to send any comments or questions to [email protected] Thank you! Gustavo Lau Answers Worksheet 1 - Going round in circles Charlie said: "It's Sunday today, so it will be Sunday again in 7 days.. and in 770 days... and in 140 days... and in 35035 days... and in 14000000007 days!" Alison said: "and it will be Tuesday in 2 days... and in 72 days... and in 702 days... and in 779 days... and in 14777002 days!" 1) Do you agree with all of Charlie's and Alison's statements? Yes. 2) Charlie and Alison chose numbers that were easy to work with. Can you see why they were chosen? Charlie’s numbers are multiples of 7 and Alison’s are (multiples of 7) + 2. 3) If today is Sunday, what day will it be in 15 days? 26 days? 234 days? 1000? We need to find the remainder of 15, 26, 234 and 1000 when divided by 7. As we don’t need the quotient we don’t need to do the division. We can find the remainders writing the numbers as (multiples of 7) plus smaller numbers: In 15=14+1 days it will be Monday. In 26=21+5 days it will be Friday. In 234=210+21+3 days it will be Wednesday. In 1000=700+280+14+6 days it will be Saturday. 4) If your birthday fell on a Sunday this year, what day will it fall on next year? Note that 365 = 350 + 15 = 350 + 14 + 1 = (multiple of 7) + 1. If the next 365 days do not include 29/February it will fall on a Monday. If the next 365 days include 29/February it will fall on a Tuesday. If your birthday is on 29/February…? 5) If it is autumn now, what season will it be in 100 seasons? Autumn as 100 is a multiple of 4. Answers 1 6) If it is 9 am now, what time will it be in 50 hours? 11 am as 50 = 48 + 2 = (multiple of 12) + 2. 7) If it is November, what month will it be in 1000 months? We need to find the remainder of 1000 when divided by 12. As we don’t need the quotient we don’t need to divide. We can find the remainder writing 1000 as (multiples of 12) plus smaller numbers: 1000 = 600 + 400 = 600 + 360 + 40 = 600 + 360 + 36 + 4 So the remainder is 4. November + 4 months is March, therefore the answer is March. 8) If it is midday now, will it be light or dark in 539 hours? We need to find the remainder of 1000 when divided by 24. We write 539 as (multiples of 24) plus smaller numbers: 539 = 480 + 59 = 480 + 48 + 11 In 11 hours, and in 539 hours, it will be dark. 9) A railway line has 27 stations on a circular loop. If I fall asleep and travel through 312 stations, where will I end up in relation to where I started? We need to find the remainder of 312 when divided by 27. We write 312 as (multiples of 27) plus smaller numbers: 312 = 270 + 42 = 270 + 27 + 15 I will end up 15 stations from where I started. 10) If a running track is 400 metres around, where will I be in relation to the start after running 6 miles (approximately 9656 metres)? We need to find the remainder of 9656 when divided by 400. We write 9656 as (multiples of 400) plus smaller numbers: 9656 = 8000 + 1656 = 8000 + 1600 + 56 I will be approximately 56 metres from the start. 11) I was facing North and then spun around through 945° clockwise. In what direction was I facing at the end? We need to find the remainder of 945 when divided by 360. We write 945 as (multiples of 360) plus smaller numbers: 945 = 720 + 225 Now 225 = 180 + 45, so at the end I am facing southwest. 12) If I get on at the bottom of a fairground wheel and the wheel turns through 5000°, whereabouts on the wheel will I be? We need to find the remainder of 5000 when divided by 360. We write 5000 as (multiples of 360) plus smaller numbers: 5000 = 3600 + 1400 = 3600 + 720 + 680 = 3600 + 720 + 360 + 320 I will be 320° from (or 40° to) the bottom of the fairground wheel. Answers 2 Worksheet 2 - Remainders and congruences 1) Find the remainders modulo 3 of: a) 31 31= 30 + 1 1 as 31 is (multiple of 3) + 1 b) 44 44 = 30 + 12 + 2 2 as 44 is (multiple of 3) + 2 c) 75 0 as 75 is multiple of 3 d) 751 751 = 750 + 1 1 as 751 is (multiple of 3) + 1 2) Find the remainders modulo 2 of: a) 34 – 15 mod 2: 0 – 1 = 1 b) 141 – 78 mod 2: 1 – 0 = 1 c) 519 – 444 + 37 mod 2: 1 – 0 + 1 = 0 3) Find the remainders modulo 12 of: a) 31 + 28 + 31 + 30 mod 12: 7 + 4 + 7 + 6 = 24 ≡ 0 b) 38 x 4 + 360 mod 12: 2 x 4 + 0 = 8 c) 66 + 5 + 26 mod 12: 6 + 5 + 2 = 13 = 12 + 1 ≡ 1 4) Which of the following congruences are true? a) 177 ≡ 17 (mod 2) Yes, because when we replace the numbers by their remainders modulo 2: 1 ≡ 1 (mod 2) Another way: 177 – 17 = 160 is even so 177 ≡ 17 (mod 2) Answers 3 b) 1322 ≡ 5294 (mod 12) 5294 – 1322 = 3972 3972 = 3600 + 360 +12 Given that 3600 ≡ 360 ≡ 12 ≡ 0 (mod 12) we have: 3972 ≡ 0 (mod 12) Therefore 1322 ≡ 5294 (mod 12) c) 16 + 30 ≡ 2 (mod 2) Yes, because when we replace the numbers by their remainders modulo 2: 0 + 0 ≡ 0 (mod 2) Another way: 16 + 30 - 2 = 44 is even so 16 + 30 ≡ 2 (mod 2) d) 16 + 30 ≡ 2 (mod 3) When we replace the numbers by their remainders modulo 3 we get: 1 + 0 ≡ 2 (mod 3) and this is false. Another way: 16 + 30 - 2 = 44 and 44 is not a multiple of 3, therefore 16 + 30 and 2 are not congruent modulo 3. 5) Which of the following congruences are true? a) 16 + 30 ≡ 2 (mod 12) When we replace the numbers by their remainders modulo 12 we get: 4 + 6 ≡ 2 (mod 12) and this is false. b) 67 x 73 ≡ 0 (mod 3) When we replace the numbers by their remainders modulo 3 we get: 1 x 1 ≡ 0 (mod 3) and this is false. c) 14 x 15 x 16 ≡ 6 (mod 3) When we replace the numbers by their remainders modulo 3 we get: 2 x 0 x 1 ≡ 0 (mod 3) and this is true. Answers 4 Worksheet 3 - Addition and multiplication tables Modulo 4 addition table: + 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 Modulo 4 multiplication table: x 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1 3 3 4 5 6 0 1 2 4 4 5 6 0 1 2 3 Modulo 7 addition table: + 0 1 2 3 4 5 6 Answers 0 0 1 2 3 4 5 6 1 1 2 3 4 5 6 0 2 2 3 4 5 6 0 1 5 5 6 0 1 2 3 4 6 6 0 1 2 3 4 5 5 Modulo 7 multiplication table: x 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 2 0 2 4 6 1 3 5 3 0 3 6 2 5 1 4 4 0 4 1 5 2 6 3 3 3 4 0 1 2 4 4 0 1 2 3 5 0 5 3 1 6 4 2 6 0 6 5 4 3 2 1 Modulo 5 addition table: + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 Modulo 5 multiplication table: x 0 1 2 3 4 Answers 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 6 Modulo 6 addition table: + 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4 4 0 4 2 0 4 2 5 0 5 4 3 2 1 Modulo 6 multiplication table: x 0 1 2 3 4 5 Answers 0 0 0 0 0 0 0 1 0 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 3 0 3 7 Worksheet 4 - Divisibility 1) Which of these numbers is not a multiple of 3? A 87 B 765 C 6543 D 43210 87: 8+7=15 is a multiple of 3. 765: 6 is a multiple of 3 so we can ignore it, 7+5=12 is a multiple of 3. 6543: We can ignore 6 and 3 (multiples of 3), 5+4=9 is a multiple of 3. 43210: Ignore 3 and 0, 4+2+1=7 is not a multiple of 3. 2) The number 1d3456 is a multiple of 9. Which digit is represented by d? 6+3=9 and 5+4=9, therefore 1+d is a multiple of 9, hence d = 8. 3) The number 1234d6 is a multiple of 11. Which digit is represented by d? -1 + 2 - 3 + 4 - d + 6 = 8 - d is a multiple of 11, therefore d = 8 (remember that 0 is a multiple of any integer). 4) The first and fourth digits of the number d63d2 are the same and the number d63d2 is a multiple of 9. Which digit is represented by d? 6+3=9, therefore d + d + 2 is a multiple of 9, therefore d = 8. 5) A four-digit number was written on a piece of paper. The last two digits were then blotted out (as shown). If the complete number is exactly divisible by three, by four, and by five, what is the sum of the two missing digits? 8 6 Given that the number is multiple of 4 and 5 it has to be a multiple of 20. Therefore it ends in 00, 20, 40, 60 or 80. If we call the 3rd digit x then we have that 8+6+x+0 = x + 14 has to be a multiple of 3. Of the five possibilities for x (0, 2, 4, 6 and 8) only x=4 satisfies that (x+14 is a multiple of 3). Then the last two digits are 4 and 0 and their sum is 4. Answers 8 6) Based on the following table of the remainders of the powers of 10: mod 1010 109 108 107 106 105 104 103 102 101 100 2 0 0 0 0 0 0 0 0 0 0 1 3 1 1 1 1 1 1 1 1 1 1 1 4 0 0 0 0 0 0 0 0 0 2 1 5 0 0 0 0 0 0 0 0 0 0 1 6 4 4 4 4 4 4 4 4 4 4 1 7 4 6 2 3 1 5 4 6 2 3 1 8 0 0 0 0 0 0 0 0 4 2 1 9 1 1 1 1 1 1 1 1 1 1 1 10 0 0 0 0 0 0 0 0 0 0 1 11 1 -1 1 -1 1 -1 1 -1 1 -1 1 12 4 4 4 4 4 4 4 4 4 10 1 a) Could you explain why looking at the last digit is enough for the divisibility criteria by 2, 5 and 10? All the powers of 10, except 100, are multiples of 2 (they are 0 modulo 2). Therefore for every natural number N: N ≡ last digit of N (mod 2) In particular, N is divisible by 2 if and only if its last digit is divisible by 2. The same argument proves that N is divisible by 5 if and only if its last digit is divisible by 5 (that is if it is 0 or 5) and that N is divisible by 10 if and only if its last digit is divisible by 10 (that is if it is 0). b) Could you give a rule to find the remainders modulo 4? All the powers of 10, except 100and 101, are multiples of 4, that is they are 0 modulo 4. 101 is 2 modulo 4 and 100is 1 modulo 4. Therefore for every natural number N: N ≡ 2*tens digit of N + last digit of N (mod 4) c) Could you give a rule to find the remainders modulo 6? All the powers of 10, except 100, are 4 modulo 6 while 100 is 1 modulo 6. Therefore for every natural number N: N ≡ 4x(sum of digits of N except the last one) + last digit of N (mod 6) Example: 461 ≡ 4x(4+6)+1 = 41 = 36+5 ≡ 5 (mod 6) Answers 9 7) From 1,001=7x11x13 we can conclude that: 1,000 ≡ –1 (mod 7) 1,000 ≡ –1 (mod 11) 1,000 ≡ –1 (mod 13) Therefore we have the following table of remainders of the powers of 1,000: mod 1015 1012 7 -1 1 11 -1 1 13 -1 1 109 -1 -1 -1 106 1 1 1 103 -1 -1 -1 100 1 1 1 Based on that table could you give divisibility criteria by 7, 11 and 13 that work for numbers greater than 1,000? Take any number greater than 1,000, say 3,918,915, then we have: 3,918,915 = 3x106+ 918x103+ 915 ≡ 3 - 918 + 915 ≡ 0 (mod 7) In general we have: N ≡ alternate sum of its groups of 3 digits of N (mod 7) where the groups have to be taken starting from the right. In particular, N is divisible by 7 if and only if the alternate sum of its groups of 3 digits is divisible by 7. This is also true mod 11 and mod 13. More examples: 243,543,348. Given that 243 – 543 + 348 = 48 we have 243,543,348 ≡ 48 ≡ 6 (mod 7) 243,543,348 ≡ 48 ≡ 4 (mod 11) 243,543,348 ≡ 48 ≡ 9 (mod 13) 315,535,220. Given that 315 – 535 + 220 = 0 we conclude that 315,535,214 is a multiple of 7, 11 and 13. 45,032. Given that -45 +32 =-13 we conclude that 45,032 ≡ -6 ≡ 1 (mod 7) 45,032 ≡ -2 ≡ 9 (mod 11) 45,032 ≡ 0 (mod 13) Answers 10 Worksheet 5 - Powers 1) Given that the modulo 10 multiplication table is: x 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 8 9 2 0 2 4 6 8 0 2 4 6 8 3 0 3 6 9 2 5 8 1 4 7 4 0 4 8 2 6 0 4 8 2 6 5 0 5 0 5 0 5 0 5 0 5 6 0 6 2 8 4 0 6 2 8 4 7 0 7 4 1 8 5 2 9 6 3 8 0 8 6 4 2 0 8 6 4 2 9 0 9 8 7 6 5 4 3 2 1 Which of the following are square numbers? a) 6312 b) 4553 c) 9538 None. The square numbers can only have 0, 1, 4, 5, 6 or 9 as last digit (the numbers in the diagonal from top left to bottom right). 2) What is the last digit of: a. 123453 5 b. 25013 0 c. 451 4 (51 is odd, it would be 6 for an even power) 3) What is the last digit of: a. 957 9 (57 is odd) b. 972 1 (72 is even) Answers 11 c. 3210 We only need to look at the last digit of 32: 2. For n>0, the last digit of 2n is: 2 if n is (multiple of 4) + 1 4 if n is (multiple of 4) + 2 8 if n is (multiple of 4) + 3 6 if n is multiple of 4 10 is a (multiple of 4) + 2, therefore the answer is 4. d. 2360 We only need to look at the last digit of 23: 3. For n>0, the last digit of 3n is: 3 if n is (multiple of 4) + 1 9 if n is (multiple of 4) + 2 7 if n is (multiple of 4) + 3 1 if n is multiple of 4 60 is a multiple of 4, therefore the answer is 1. 4) What is the remainder when dividing… a. …1080 by 9? 1 because 10 ≡ 1 (mod 9) b. …69770 by 5? 1 because 6 ≡ 1 (mod 5) c. …584320 by 4? 1 because 5 ≡ 1 (mod 4) d. …493184 by 4930? 1 because 4931 ≡ 1 (mod 4930) 5) What is the remainder when dividing 51001 by 6? Hint: 5 ≡ –1 (mod 6). Given that 5 ≡ –1 (mod 6) we have that 5n ≡ 1 (mod 6) if n is even 5n ≡ -1 ≡ 5 (mod 6) if n is odd 1001 is odd, therefore 51001 ≡ 5 (mod 6), so the remainder when dividing 51001 by 6 is 5. 6) What is the remainder when dividing 212035981234808093146372789686129386749 by 3? Given that 2 ≡ –1 (mod 3) we have that 2n ≡ 1 (mod 3) if n is even 2n ≡ -1 ≡ 2 (mod 3) if n is odd The exponent 12035981234808093146372789686129386749 is odd, therefore 212035981234808093146372789686129386749 ≡ 2 (mod 3), so the remainder when dividing 212035981234808093146372789686129386749 by 3 is 2. Answers 12 Worksheet 6 - Day of the week 1) What are the weekdays of: a. 23/Apr/1999 Remember that 1995 has code 0. 1999 code ≡ 99-95 + number of leap years in 1996-1999 (mod 7) 1999 code ≡ 4 + 1 (mod 7) (only 1996 was a leap year in 1996-1999) 1999 code = 5 Apr has code 5 and 5+5+23=33 ≡ 5 (mod 7), therefore 23/Apr/1999 was a Friday. b. 14/May/1989 Remember that 1989 has code 0. May has code 0 and 0+0+14 ≡ 0 (mod 7), therefore 14/May/1989 was a Sunday. c. 1/Jan/1999 1999 code = 5 (see a. above) 1999 was non-leap so Jan code is 6, 5+6+1=12≡ 5 (mod 7), therefore 1/Jan/1999 was a Friday. d. 1/Jan/2000 2000 code = 0 2000 was leap so Jan code is 5, 0+5+1=6≡ 5 (mod 7), therefore 1/Jan/2000 was a Saturday. e. 3/Feb/1999 1999 code = 5 (see a. above) 1999 was non-leap so Feb code is 2, 5+2+3=10≡ 3 (mod 7), therefore 3/Feb/1999 was a Wednesday. f. 3/Feb/2000 2000 code = 0 2000 was leap so Feb code is 1, 0+1+3=4, therefore 3/Feb/2000 was a Thursday. Answers 13