Homework Help is Here – Start Your Trial Now!
Math
Advanced Math
3. Suppose that p and q are odd primes. Show that pq is a pseudoprime base 2 if and only if ord, (2)| (q-1) and ord, (2) | (p-1). Here, if gcd(a, p) = 1, we use the notation ord,(a) for the order of the element [a], in the group Up.

3. Suppose that p and q are odd primes. Show that pq is a pseudoprime base 2 if and only if ord, (2)| (q-1) and ord, (2) | (p-1). Here, if gcd(a, p) = 1, we use the notation ord,(a) for the order of the element [a], in the group Up.

Advanced Engineering Mathematics
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
See similar textbooks
icon
Related questions
Question

[Number Theory] How do you solve question 3? The second picture is for definitions. thanks

Additional information:

  • We say that a group G is abelian if its elements commute, that is, gh = hg for all g, h in  G
  • Un is an abelian group under multiplication mod (n)
1. (i) Show by hand that 2 is a primitive root mod 19. (ii) Find² a complete set of primitive roots mod 19. 2. Suppose that a and b are primitive root modulo an odd prime p. Show that ab is not a primitive root mod p. 3. Suppose that p and q are odd primes. Show that pq is a pseudoprime base 2 if and only if ord, (2)| (q-1) and ord, (2)| (p-1). Here, if gcd(a, p) = 1, we use the notation ord, (a) for the order of the element [a], in the group Up. 4. (i) Show that 2 is a primitive root mod 11² = 121. Hint: Use the criterion given by Lemma 6.4 and a calculator. Conclude that 2 is a primitive root mod 11e for any e. (ii) How many elements of order 5 are there in the group U1331? Note that 1331 = 11³. (iii) Find all elements of order 5 in U1331. ¹1.e., do not use a calculator Here you may use a calculator to compute residues mod 19.
Transcribed Image Text:1. (i) Show by hand that 2 is a primitive root mod 19. (ii) Find² a complete set of primitive roots mod 19. 2. Suppose that a and b are primitive root modulo an odd prime p. Show that ab is not a primitive root mod p. 3. Suppose that p and q are odd primes. Show that pq is a pseudoprime base 2 if and only if ord, (2)| (q-1) and ord, (2)| (p-1). Here, if gcd(a, p) = 1, we use the notation ord, (a) for the order of the element [a], in the group Up. 4. (i) Show that 2 is a primitive root mod 11² = 121. Hint: Use the criterion given by Lemma 6.4 and a calculator. Conclude that 2 is a primitive root mod 11e for any e. (ii) How many elements of order 5 are there in the group U1331? Note that 1331 = 11³. (iii) Find all elements of order 5 in U1331. ¹1.e., do not use a calculator Here you may use a calculator to compute residues mod 19.
Definition If Un is cyclic then any generator g for Un is called a primitive root mod (n). This means that g has order equal to the order (n) of Un, so that the powers of g yield all the elements of Un. For instance, 2 and 3 are primitive roots mod (5), but there are no primitive roots mod (8) since Us is not cyclic. Finding primitive roots in Un (if they exist) is a non-trivial problem, and there is no simple solution. One obvious but tedious method is to try each of the (n) units a E Un in turn, each time computing powers a' mod (n) to find the order of a in Un; if we find an element a of order (n) then we know that this must be a primitive root. The following result is a rather more efficient test for primitive roots: Lemma 6.4 An element a E Un is a primitive root if and only if a(n)/9 ‡ 1 in Un for each prime q dividing (n).
Transcribed Image Text:Definition If Un is cyclic then any generator g for Un is called a primitive root mod (n). This means that g has order equal to the order (n) of Un, so that the powers of g yield all the elements of Un. For instance, 2 and 3 are primitive roots mod (5), but there are no primitive roots mod (8) since Us is not cyclic. Finding primitive roots in Un (if they exist) is a non-trivial problem, and there is no simple solution. One obvious but tedious method is to try each of the (n) units a E Un in turn, each time computing powers a' mod (n) to find the order of a in Un; if we find an element a of order (n) then we know that this must be a primitive root. The following result is a rather more efficient test for primitive roots: Lemma 6.4 An element a E Un is a primitive root if and only if a(n)/9 ‡ 1 in Un for each prime q dividing (n).
Expert Solution
steps

Step by step

Solved in 3 steps with 1 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
Basic Technical Mathematics
Basic Technical Mathematics
Advanced Math
ISBN:
9780134437705
Author:
Washington
Publisher:
PEARSON
Topology
Topology
Advanced Math
ISBN:
9780134689517
Author:
Munkres, James R.
Publisher:
Pearson,
SEE MORE TEXTBOOKS