[PDF] MATH 115A SOLUTION SET V FEBRUARY 17 2005 (1) Find the

View - Download MATH 115A SOLUTION SET V FEBRUARY 17 2005 (1) Find the

Previous PDF

Next PDF

MATH 115A SOLUTION SET V

FEBRUARY 17, 2005

(1) Find the orders of the integers 2, 3 and 5: (a) modulo 17; (b) modulo 19; (c) modulo 23.

Solution:

(a) Euler"s theorem implies that it suffices to consider exponents which are divisors of 16.

Working modulo 17 gives

2

2≡4,24≡16,28≡1,

3 5 Hence it follows that 2, 3, and 5 have orders 8, 16 and 16 respectively. (b) Consider the divisors 2, 3, 6 and 9 of 18. Working modulo 19 gives 2 3 5

2≡6,53≡11,56≡7,59≡1.

Hence it follows that 2, 3, and 5 have orders 18, 18 and 9 respectively. (c) Using the exponents 2, 11 and 22, and working modulo 23 gives 2

2≡4,211≡1

3

2≡9,311≡1

5

2≡2,511≡22,522≡1.

Thus 2, 3, and 5 have orders 11, 11 and 22 respectively. (2) Establish each of the following statements below: (a) Ifahas orderhkmodulon, thenahhas orderkmodulon. (b) Ifahas order 2kmodulo an odd primep, thenak≡ -1 modp.

Solution:

(a) Assume thatahas orderhk(modn), so thatahk≡1 (modn), butam?≡1 (modn) for 0< m < hk. Since (ah)k≡1 (modn), it follows that the elementahhas order at most k.

Now if the order ofahisr, with 0< r < k, then

a hr= (ah)r ≡1 modn, 1

2 MATH 115A SOLUTION SET V FEBRUARY 17, 2005

and this is impossible, sincehr < hk. Hence it follows thatahhas orderk(modn). (b) Suppose thatahas order 2k(modp), wherepis an odd prime. Then a

2k≡1 (modp) (1)

butam≡1 (modp) for 0< m < p. Equation (1) implies thatp|(a2k-1), i.e. that p|(ak-1)(ak+ 1). Therefore eitherak≡1 (modp), orak≡ -1 (modp). However the former possibilty cannot occur, sinceahas order 2k(modp). It therefore follows that a k≡ -1 (modp), as claimed. (3) Prove thatφ(2n-1) is a multiple ofnfor anyn≥1. [Hint: The integer 2 has order nmodulo 2n-1.]

Solution:

Plainly we have that 2

implies that 2 k?≡1 (mod 2n-1), for otherwise we would have (2n-1)|(2k-1), which is impossible. Hence it follows that the order of 2 (mod 2 n-1) is equal ton. By Euler"s theorem, we have 2

φ(2n-1)≡1 (mod 2n-1),

and so it follows thatn|φ(2n-1). (4) Prove the following assertions: (a) The odd prime divisors of the integern2+ 1 are of the form 4k+ 1. [Hint: Ifpis an odd prime, thenn2≡ -1 modpimplies that 4|φ(p).] (b) The odd prime divisors of the integern4+ 1 are of the form 8k+ 1.

Solution:

(a) Suppose thatpis an odd prime divisor ofn2+ 1, so thatn2≡ -1 modp. This implies thatn4≡1 modp. Euler"s theorem tells us that 4φ(p)≡1 modp, i.e. that 4 p-1≡1 modp. Hence it follows that 4|(p-1), and sop= 4k+ 1 for somek. (b) Ifpis an odd prime divisor ofn4+ 1, thenn4≡ -1 modp, and son8≡1 modp. Hence, arguing just as in part (a), it follows that 8|(p-1), i.e. thatp= 8k+ 1 for some k. (5) Letrbe a primitive root modulop, wherepis an odd prime. Prove the following: (a) The congruencer(p-1)/2≡ -1 (modp) holds. (b) Ifr?is any other primitive root modulop, thenrr?is not a primitive root modulop. [Hint: From part (a), (rr?)(p-1)/2≡1 (modp).] (c) If the integerr?is such thatrr?≡1 (modp), thenr?is also a primitive root modulo p.

Solution:

(a) Sinceris a primitive root modulop,rp-1≡1 (modp), andp-1 is the smallest integer with this property. We deduce thatp|(rp-1-1), i.e.p|[(r(p-1)/2-1)(r(p-1)/2+1)]. Hence eitherr(p-1)/2≡1 (modp) orr(p-1)/2≡ -1 (modp). The first possibilty contradicts the fact thatris a primitive root modulop. Thereforer(p-1)/2≡ -1 (modp) as claimed. (b) Ifrandr?are primitive roots modulo an odd primep, then by part (a), (rr?)(p-1)/2≡r(p-1)/2(r?)(p-1)/2≡ -1· -1≡1 (modp).

MATH 115A SOLUTION SET V FEBRUARY 17, 2005 3

Hencerr?has order at most (p-1)/2 modulop, and so cannot be a primitive root modulo p. (c) By Fermat"s Little Theorem, we have (r?)p-1≡1 (modp). If the order ofr?modulo which contradicts the fact thatris a primitive root modulop. Therefore the order ofr? modulopis equal top-1, and sor?is a primitive root modulop. (6) For any primep >3, prove that the primitive roots modulopoccur in incongruent pairsr,r?, whererr?≡1 (modp). [Hint: Ifris a primitive root modulop, consider the integerr?=rp-2.]

Solution:

Letrbe a primitive root modulo the primep >3, and setr?=rp-2. Thenrr?=r·rp-2=quotesdbs_dbs3.pdfusesText_6

[PDF] modulo 11

[PDF] calcul modulo 23

[PDF] clé de contrôle sécurité sociale

[PDF] 11 modulo 10

[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é