Introduction To Modular Arithmetic

1 Introduction To Modular ArithmeticFebruary 22, 2015 Olga RadkoOleg Up ProblemIt takes a grandfather s clock30seconds to chime6o clock. Assuming that the time of eachchime is negligible compared to the time intervals between the chimes, how much time wouldit take the clock to chime12?Clock Arithmetic or a Circle as a Number LineOne way to turn a circle into a number line is to divide it into twelve equal parts. In this case,one step is usually called one 2It takes a grandfather s clock 30 seconds to chime6 o clock. How much time would it take the clock to chime 12?Clock Arithmetic or a Circle as a Number LineOne way to turn a circle into a number line is to divide itinto twelve equal parts. In this case, one step is usually calledone coincides with 12. The hour hand moves from 0 to 1, from1to2.

2 From11to12justasitwouldhaveonthestraight number line. However, 12 equals 0 on this circle, so there it goes2 Notice that0coincides with12,andasthehourhandmovestotheright,1 coincides with13,2with14, and so on. The hour hand rotates clockwise which corresponds with numbersincreasing when moving to the right on a number line. However,12is equivalent to0on thiscircle, which can be written as follows:12 0(mod 12).1 This can be read as12 is congruent to 0 modulo usual = sign is reserved for thestraight number line; we use on the circle instead. The symbol mod 12 tells us thatthe circle is divided into12equal parts, so that12coincides with0,13with1, notation we have:12 0(mod 12),13 1(mod 12),..23 11 (mod 12) reduce the following numbers in Modular Arithmetic .(a)18 (mod 12)(b)25 (mod 12)(c)36 (mod 12) that if you move to the left of0on a number line, you get negative , going in the opposite direction (counterclockwise) on the number circle, we getto negative numbers in Modular Arithmetic .

3 For example, 1 11 (mod 12), 25 10 (mod 12).Use this to reduce the following numbers in mod12arithmetic (note that all answersmust be between0and11).(a) 2 (mod 12)(b) 4 (mod 12)(c) 19 (mod 12) can also divide the clock into60equal parts. Depending on the situation, a unit stepis called either a minute or a second. All of the numbers living on this number circle areconsidered modulo60. More specifically,60 0(mod 60), which corresponds to the factthat there are 60 minutes in an hour (or 60 seconds in a minute).Reduce the following numbers in mod60arithmetic.(a)72 (mod 60)(b)135 (mod 60)(c) 15 (mod 60)(d) 80 (mod 60) is the time, in hours, minutes, and seconds, on the clock below?Problem572 (mod60) 135 (mod60) 55 + 55 (mod60)240 59 (mod60)Problem6 What is the time, in hours, minutes, and seconds,on the clock below?

4 32112111098765415105055504540353025205 Notice that since60 = 12 5, the same marks can be used to indicate a whole numberof hours and a number of minutes which is a multiple of5.(Forexample,the4hourmark is the same as the20minute mark).The24-HourClockThere are24hours in a day, so one more standard way to turn a circle into a number lineis to divide it into24equal parts. The US military uses the24hour clock. The followingis a photograph of the24hour clock from the USS (United States Ship) are 24 hours in a day, so one more standard way toturn a cricle into a number line is to divide it into 24 equalparts. The US military use the 24-hour clock. The following isa photograph of the 24-hour clock from the USS (United StatesShip)Mullinnix, the last all gun US Navy destroyer in thePacific, decommissioned in its homepage not a multiple of24,wecan tusethesamemarksonthefaceofa24hourclock for minutes and hours (look at the minute marks on the face of the 24 hour clock).

5 Time does the USS Mullinex clock show on the previous page? is the time on the clock shown below?Since 60 24 is not a whole number, we can t use the samemarks on the face of a 24-hour clock for minutes and hours (tobetter see this, please find the minute and hour marks on the faceof the USSM ullinnixclock). 60 12 = 5, so this inconveniencedoesn t exist for the clocks and watches we are used to. On theother hand, to disambiguate between, say, 1 o clock night timeand 1 o clock afternoon, we have to use the notationnot needed in the military. In their language, 1 o clock is13:00 (thirtheen hundred) hours, plain and time does the USS Mullinnix clock show?Problem8 What is the time on the clock below?3211211109876541510505550454035302 5207If this time is in , how would the military call this time?

6 The left, draw the12hour clock showing7 On the right, draw the militaryclock showing the same that this is the time How would the militarycall it?Problem9On the left, draw the civilian clock showing 1 the right, draw the military clock showing the same ArithmeticIn addition to clock analogy, one can view Modular Arithmetic asarithmetic of example, in mod12arithmetic, all the multiples of12( , all the numbers that giveremainder0when divided by12)areequivalentto0. Inthemodulararithmeticnotation,this can be written as12 n 0(mod 12) for any whole , all numbers that give remainder1when divided by12are equivalent to 1. Inother words,12 n+1 1(mod 12) for any whole that any whole numberacan be uniquely written in the forma=12 n+rwhereris one of the numbers0,1,.., the remainder of the divisionofaby12.

7 Therefore,a r(mod 12). For example, 50 = 5 12 + 10, which implies 50 10(mod 12),40 = 3 12 + 4, which means40 4(mod 12). the following numbers in the forma=12 n+ in mod12arithmetic.(a)45 = 12 +,45 (mod12).(b)80 =(c) 18 =(d) 61 = the following negative numbers in mod12arithmetic.(a) 11 (mod 12)(b) 10 (mod 12)(c) 9 (mod 12)(d) 3 (mod 12)(e) 2 (mod 12)(f) 1 (mod 12)(g)What do you notice? If you are given a negative number between 12and 1,howdo you reduce it in mod12arithmetic? Why is this true?(h)Using your answer to part (g), complete the following formula k (mod 12)wherek=1,.., to how we used12and60as a modulus for Modular Arithmetic , any positiveinteger can be used. Moreover, we can define operations of addition and multiplicationin the Modular Arithmetic : To add two numbers in Modular Arithmetic , add them in the ordinary sense and thenreduce (if necessary) in Modular Arithmetic ; To multiply two numbers in Modular Arithmetic , multiply them in the ordinary senseand then reduce (if necessary) in Modular Arithmetic ;Fill in the addition and multiplication tables below in modn, wheren=4,n=5,andn= (a)n=4+01230123x01230123(b)n=5:+01234012 34x0123401234(c)n=7:+ and multiplication are straightforward operations.

8 Solving problems involvingsubtraction can be a little more difficult. We know that subtraction is the operationopposite to addition. For example, in the ordinary Arithmetic , to subtract3from4means to find a numbercsuch that4=3+c. More generally,a b=cmeans thata=b+.Subtraction in the Modular Arithmetic is defined in a similar the following subtraction problems in Modular Arithmetic .(a)2 3 (mod 4)(b)3 6 (mod 7)(c)1 2 (mod 3)Now check your answers using addition in Modular Arithmetic .(a)2 3+(mod 4)(b)3 6+(mod 7)(c)1 2+(mod3) is the operation opposite to multiplication . For example, in ordinary Arithmetic ,to divide3by4means to need to find a numbercsuch thatc 4= ,inmodulo7,todivide3by4means to find a numbercsuch that:c 4 3(mod 7).cmust be equivalent to one of the numbers0,1, ,6in you made problem10(c), we see thatc 6(mod 7).

9 Thus, we write3 4 6(mod 7)This is true because6 4 3(mod 7).Please solve the following division problems in Modular Arithmetic (remember to use thetables you made).(a)1 2 (mod 7)(b)1 4 (mod 7)(c)2 3 (mod 7)(d)4 5 (mod 7)(e)5 6 (mod 7)(f)1 3 (mod 5)(g)How could you solve part (f) without using the tables? (Hint: Use the fact that inmod Arithmetic ,1can be replaced by any number which gives remainder1whendivided by5)9 Zero regular Arithmetic , we know that if a product of two numbers is zero, then at leastone of the numbers is zero. In Modular Arithmetic , this is not always the case.(a)Find two non-zero numbers in mod4arithmetic such that their product is0.(b)Find two non-zero numbers in mod6arithmetic such that their product the product of two non-zero numbers is equivalent to zero in Modular Arithmetic ,these numbers are calledzero zero divisors in modn, wherexandycan be the numbers0.

10 ,n 1,what can be said about the value ofx y? all zero divisors in mod12arithmetic. Explain your there any zero divisors in mod7arithmetic? Explain your a biology experiment begins at7 and runs for80hours, at what time will itend? s birthday lies on a Monday this year. What day of the week will his birthday beon in2016? the following numbers using Modular Arithmetic :(a)136283 192758237582389 (mod 2)(b)19342347328 + 1894837483 (mod 10)(c)1934232 1894837480 (mod 10) hot dog buns come in packages of 34, and hot dogs come in packages of8.(a)What is the smallest number of packages of hot dogs and hot dog buns Ivy shouldbuy if she doesn t want to have left-over hot dogs or left-over hot dog buns? (Assumethat hot dogs can t be eaten without a bun, or vice versa).(b)Suppose that hot dog buns come in packages of 33.