[PDF] Everything You Need to Know About Modular Arithmetic

Everything You Need to Know About Modular Arithmetic

modulo 10 while 5 is not relatively prime to 10 and therefore has no inverse modulo 10 Ex 5 We can compute which numbers will have inverses modulo 10 by computing which are relatively prime to 10 = 5·2 These numbers are x = 1,3,7,9 It is easy to see that the following table gives inverses module 10: 2

Math 110 Homework 4 Solutions

powers of agenerate all units modulo p The primitive roots are 2;6;7;8 (mod 11) To check, we can simply compute the rst ˚(11) = 10 powers of each unit modulo 11, and check whether or not all units appear on the list A more sophisticated approach: Once you have a primitive root a(mod 11), it’s a fact that the other primitive roots must be

EECS 203-1 Homework 10 Solutions Total Points: 30

14) a) Show that the positive integers less than 11, except 1 and 10, can be split into pairs of integers such that each pair consists of integers that are inverses of each other modulo 11 b) Use part (a) to show that 10 -1 (mod 11) 6 points a) We know that each of the integers 1, 2, 3 10 has an inverse modulo 11 (because 11 is prime)

Math 110 Problem Set 2 Solutions

root mod 11 (b) Note that the inverse of 3 (mod 10) is 7 (mod 10) Now, by Fermat’s Little Theorem, 210 · 1 (mod 11) Thus, 23 · 8 (mod 11))(23)7 · 87 (mod 11))87 · 221 · 2 (mod 11) Thus, the x we want is 7 (c) Let c be a congruence class mod 11 By (a), there exists x such that 2x · c (mod 11) Applying the formula from (b), we have

CHECK DIGITS - An application of MODULAR ARITHMETIC

10 is the check digit 0 10 4 9 7 8 1 7 3 6 1 5 0 4 5 3 5 2 7 1 { 0 mod 11 ISBN 0-471-31055-7 This detects all single digit errors and all transpositions of adjacent digits The only drawback is that the “check digit” could be “10” which is not a single digit In this case one uses “X”: 0 10 4 9 7

Socioemocional - Proyecto Alcanza

3 INTRODUCCIÓN Annette López de Méndez, Ed D Directora Proyecto ALCANZA Para crecer bien, es de suma importancia atender los aspectos físico, cognitivo y emocional

13 Congruences - NIU

39 Prove that 10n+1 +4 ·10n +4 is divisible by 9, for all positive integers n Comment: This could be proved by induction, but we can give a more elegant proof using congruences Solution: The proof consists of simply observing that 10n+1+4·10n+4 ≡ 0 (mod 9) since 10 ≡ 1 (mod 9) 40 Prove that for any integer n, the number n3+5nis

Fermat’s Little Theorem Solutions - CMU

Sep 27, 2015 · x103 4 mod 11 [Solution: x 5 mod 11] By Fermat’s Little Theorem, x10 1 mod 11 Thus, x103 x3 mod 11 So, we only need to solve x3 4 mod 11 If we try all the values from x = 1 through x = 10, we nd that 53 4 mod 11 Thus, x 5 mod 11 9 Find all integers x such that x86 6 mod 29 [Solution: x 8;21 mod 29] By Fermat’s Little Theorem, x28 1

MÓDULO PARA REMEDIAR - Departamento de Educación

c 11 d 10 Estándar: Conservación y Cambio Expectativa ES BCB3 CC2: Aplica conceptos estadísticos y de probabilidad para explicar la variación y distribución de las características visibles en la población El énfasis está en el uso de las matemáticas para describir la

[PDF] calcul modulo 97

[PDF] personnage du livre moi boy

[PDF] escadrille 80 questionnaire de lecture

[PDF] controle de lecture moi boy

[PDF] moi boy roald dahl pdf entier

[PDF] moi boy roald dahl résumé

[PDF] moi boy roald dahl pdf gratuit

[PDF] séquence pluriel des noms ce2

[PDF] no et moi telecharger pdf

[PDF] leçon pluriel des noms ce2 lutin bazar

[PDF] no et moi avis argumenté

[PDF] séquence pluriel des noms ce1

[PDF] effet doppler formules

[PDF] télécharger no et moi pdf

[PDF] effet doppler formule longueur d'onde

Everything You Need to Know About Modular Arithmetic...

Math 135, February 7, 2006

DefinitionLetm >0 be a positive integer called themodulus. We say that two integersaandbare congruent modulomifb-ais divisible bym. In other words, a≡b(modm)??a-b=m·kfor some integerk.(1) Note:

1. The notation ??≡??(modm) works somewhat in the same way as the familiar ?? =??.

2.acan be congruent to many numbers modulomas the following example illustrates.

Ex. 1The equation

x≡16(mod10) has solutionsx=...,-24-14,-4,6,16,26,36,46.... This follows from equation (1) since any of these numbers minus 16 is divisible by 10. So we can write x≡ ··· -24≡ -14≡ -4≡6≡16≡26≡36≡46(mod10). Since such equations have many solutions we introduce the notationa(MODm)

DefinitionThe symbol

a(MODm) (2) denotes the smallest positive numberxsuch that x≡a(modm). In other words,a(MODm) is the remainder whenais divided bymas many times as possible. Hence in example 1 we have

6 = 16(MOD10) and 6 =-24(MOD10) etc....

Relation between "x≡bmodm" and "x=bMODm"

x≡bmodmis an EQUIVALENCE relation with many solutions forxwhilex=bMODmis an EQUALITY. So one can think of the relationship between the two as follows x=b(MODm) is the smallest positive solution to the equationx≡b(modm). Since

0< b(MODm)< m

it is convention to take these numbers as the representatives for the class of numbersx≡b(modm).

1 Ex. 2The standard representatives for all possible numbers modulo 10 are given by

0,1,2,3,4,5,6,7,8,9

although, for example, 3≡13≡23(mod 10), we would take the smallest positive such number which is 3.

Inverses in Modular arithmetic

We have the following rules for modular arithmetic: Sum rule:IFa≡b(modm) THENa+c≡b+c(modm).(3) Multiplication Rule:IFa≡b(modm) and ifc≡d(modm) THENac≡bd(modm).(4) DefinitionAn inverse toamodulomis a integerbsuch that ab≡1(modm).(5) By definition (1) this means thatab-1 =k·mfor some integerk. As before, there are may be many

solutions to this equation but we choose as a representative the smallest positive solution and say that the

inversea-1is given by a -1=b(MODm). Ex 3. 3 has inverse 7 modulo 10 since 3·7 = 21 shows that

3·7≡1(mod 10) since 3·7-1 = 21-1 = 2·10.

5 does not have an inverse modulo 10. If 5·b≡1(mod 10) then this means that 5·b-1 = 10·kfor some

k. In other words

5·b= 10·k-1 which is impossible.

Conditions for an inverse ofato exist modulom

DefinitionTwo numbers are relatively primeif their prime factorizations have no factors in common. number modulom). Thenahas a multiplicative inverse modulomifaandmare relatively prime.

Ex 4Continuing with example 3 we can write 10 = 5·2. Thus, 3 is relatively prime to 10 and has an inverse

modulo 10 while 5 is not relatively prime to 10 and therefore has no inverse modulo 10.

Ex 5We can compute which numbers will have inverses modulo 10 by computing which are relatively prime

to 10 = 5·2. These numbers arex= 1,3,7,9. It is easy to see that the following table gives inverses module

10: 2

Table 1: inverses modulo 10

x1379 x -1MOD 101739

Ex 6: We can solve the equation 3·x+ 6≡8(mod 10) by using the sum (3) and multiplication (4) rules

along with the above table:

3·x+ 6≡8(mod 10) =?

3·x≡8-6≡2(mod 10) =?

(3 -1)·3·x≡(3-1)·2(mod 10) =? x≡7·2(mod 10)≡14(mod 10)≡4(mod 10) Final exampleWe calculate the table of inverses modulo 26. First note that

26 = 13·2

so that the only numbers that will have inverses are those which are rel. prime to 26...i.e. they contain no

factors of 2 or 13:

1,3,5,7,9,11,15,17,19,21,23,25.

Now we write some multiples of 26

26,52,78,104,130,156,182,208,234...

A numberahas an inverse modulo 26 if there is absuch that a·b≡1(mod 26)ora·b= 26·k+ 1.

thus we are looking for numbers whose products are 1 more than a multiple of 26. We create the following

table

Table 2: inverses modulo 26x1357911151719212325

x -1(MODm)1921153197231151725 since (using the list of multiples of 26 above)

1·1 = 1 = 26·0 + 1

3·9 = 27 = 26 + 1

5·21 = 105 = 104 + 1

7·15 = 105 = 104 + 1

11·19 = 209 = 208 + 1

17·23 = 391 = 15·26 + 1

25·25 = 625 = 26·24 + 1.

3

So we can solve

y= 17·x+ 12(MOD 26) forxby first considering the congruence equation y≡17·x+ 12(mod 26) and performing the following calculation (similar to ex 6) using the above table: y≡17·x+ 12(mod 26) =? y-12≡17·x(mod 26) =? (17 -1)(y-12)≡(17-1)·17·x(mod 26) =? (23)(y-12)≡(23)·17·x(mod 26) =?

23·(y-12)≡x(mod 26)

We now writex= 23·(y-12)(MOD 26).

The difference between

23·(y-12)≡x(mod 26)

and x= 23·(y-12)(MOD 26)

is simply that in the first equation, a choice ofywill yield many different solutionsxwhile in the second

equation a choice ofygives the valuexsuch thatxis the smallest positive solution...i.e. the smallest positive

solution to the first equation. 4quotesdbs_dbs11.pdfusesText_17