Math 110 Problem Set 2 Solutions

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

Math 110 Problem Set 2 Solutions

3.8 Letp¸3 be prime. Show that the only solutions tox2´1 (modp) are x´ §1 (modp).

Solution:

Note that we have

Thus, by Exercise 7(a), we have that eitherx¡1´0 (modp) orx+ 1´0 (modp) so we havex´ §1 (modp) as required. 3.9 Supposex´2 (mod 7) andx´3 (mod 10). What isxcongruent to mod 70?

Solution:

This is easiest to do by trial and error. The 2nd condition means thatxis 3, 13, 23, 33, 43, 53, or 63 modulo 70. Checking, we see that the only one of these which is 2 modulo 7 is 23, soxmust be 23 (mod 70). Note that the Chinese Remainder Theorem guarantees that there is a unique answer to the question. 3.11

Letpbe prime. Show thatap´a(modp) for alla.

Solution:

Let us consider two cases:pdividesa, andpdoes not dividea. If pdividesa, then both sides are 0 modulop. Ifpdoes not dividea, by Fermat's

Little Theorem,

a p¡1´1 (modp) )ap´a(modp)

Thus, in either case,ap´a(modp)

3.12

Divide 2

10203by 101. What is the remainder?

Solution:

Note that by Fermat's Little Theorem, 2

100´1 (mod 101). Thus,

we have that for any integern, 2100n´1 (mod 101), raising both sides to the power ofn. Hence, we have that 210200´1 (mod 101), so we conclude that 2

Thus, the remainder from the division is 8.

3.15 (a) ComputeÁ(d) for all of the divisors of 10 (namely, 1, 2, 5, 10) and ¯nd the sum of all theseÁ(d). (b) Repeat part (a) for all the divisors of 12. (c) Letn¸1. Conjecture the value ofPÁ(d), where the sum is over the divisors ofn. 1

Solution:

(a) We calculate:

Á(1) = 1

Á(2) = 2¡1 = 1

Á(5) = 5¡1 = 4

Here we have used the fact thatÁ(p) =p¡1 for a primepand the formula for Á(n) in the textbook. Thus, we have that the sum of all these is 1+1+4+4 = 10. (b) We calculate:

Á(1) = 1

Á(2) = 2¡1 = 1

Á(3) = 3¡1 = 2

2 ) = 2 2 )(1¡1 3 Thus, we have that the sum of all these is 1 + 1 + 2 + 2 + 2 + 4 = 12. (c) The previous two examples suggest that this sum isn. 3.17 (a) Show that every nonzero congruence class mod 11 is a power of 2, and therefore 2 is a primitive root mod 11. (b) Note that 2

3´8 (mod 11). Findxsuch that 8x´2 (mod 11).

(c) Show that every nonzero congruence class mod 11 is a power of 8, and therefore 8 is a primitive root mod 11. (d) Letpbe prime and letgbe a primitive root modp. Leth´gy(modp) with gcd(y;p¡1) = 1. Letxy´1 (modp¡1). Show thathx´g(modp). (e) Letpandhbe as in part (d). Show thathis a primitive root modp.

Solution:

(a) Let us calculate the powers of 2 modulo 11:

2´2 (mod 11)

2´4 (mod 11)

3´8 (mod 11)

4´16´5 (mod 11)

2 2 2 2 2 2 2 Thus, we see that every congruence class mod 11 appears, so 2 is a primitive root mod 11. (b) Note that the inverse of 3 (mod 10) is 7 (mod 10). Now, by Fermat's

Little Theorem, 2

10´1 (mod 11). Thus,

3´8 (mod 11)

)(23)7´87(mod 11) )87´221´2 (mod 11)

Thus, thexwe want is 7.

(c) Letcbe a congruence class mod 11. By (a), there existsxsuch that 2x´c (mod 11). Applying the formula from (b), we have that 8

7x´c(mod 11). Thus

every nonzero congruence class mod 11 is a power of 8. (d) Sincexy´1 (modp¡1), by Fermat's Little Theorem, g xy´g(modp) )hx´(gy)x´gxy´g(modp) (e) Letcbe a congruence class modp. Then, sincegis a primitive root modp, there existsasuch thatga´c(modp). Thus, we have thathax´c(modp), so every nonzero congruence class modpis a power ofh. Hencehis a primitive root modp. 3quotesdbs_dbs11.pdfusesText_17

[PDF] Math 110 Problem Set 2 Solutions

Math 110 Problem Set 2 Solutions

Solution:

Note that we have

Solution:

Letpbe prime. Show thatap´a(modp) for alla.

Solution:

Little Theorem,

Thus, in either case,ap´a(modp)

Divide 2

10203by 101. What is the remainder?

Solution:

Note that by Fermat's Little Theorem, 2

100´1 (mod 101). Thus,

Thus, the remainder from the division is 8.

Solution:

Á(1) = 1

Á(2) = 2¡1 = 1

Á(5) = 5¡1 = 4

Á(1) = 1

Á(2) = 2¡1 = 1

Á(3) = 3¡1 = 2

3´8 (mod 11). Findxsuch that 8x´2 (mod 11).

Solution:

2´2 (mod 11)

2´4 (mod 11)

3´8 (mod 11)

4´16´5 (mod 11)

Little Theorem, 2

10´1 (mod 11). Thus,

3´8 (mod 11)

Thus, thexwe want is 7.

7x´c(mod 11). Thus