Let m e N and a E Z. Suppose that 3|(m) and that a is a primitive root (mod m). Prove that a is not a primitive root (mod m). [You must clearly write and justify the steps in your proof.]

Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
icon
Related questions
Question
Theorem 1. Let x, y, z be positive integers where x is odd and y is even. Then x, y, z is a primitive
Pythagorean triple if and only if there are positive integers u and v such that
v², y= 2uv,
z = u? + v?
(1)
where (u, v) = 1, u > v and exactly one of u and v is even.
Theorem 2 (Euler's Theorem). Let m be a natural number and let a be an integer such that
(a, m) = 1. Then aº(m) = 1 (mod m).
Theorem 3. Let m e N and let a € Z be such that (a, m) = 1. Let n be a natural number. Then
a" = 1 (mod m) if and only if om(a) |n.
(a, b). If d{ c, then the
Theorem 4. Suppose that a and b are non-zero integers and let d =
equation
ax + by = c
(2)
does not have any integer solutions. If d|c, then this equation has an infinite number of solutions.
In fact, if ro and yo is one integer solution to equation (2), then all such solutions have the form
x = xo +t
a
y = Yo – t
where t varies over the integers.
Definition 5. Let m e N and let a e Z be such that (a, m) = 1. The order (mod m) of a,
denoted by om(@), is the least d e N such that ad = 1 (mod m).
Definition 6. Let m be a natural number and let a be an integer such that (a, m)
Om (a) = 0(m), then a is said to be a primitive root (mod m).
= 1. If
Corollary 7. Let m e N. If a primitive root (mod m) exists, then there are exactly o(0(m))
incongruent primitive roots (mod m).
Theorem 8. Let p be a prime number and let d e N be such that d|(p – 1). Then there are
exactly ø(d) many incongruent integers of order d modulo p.
Corollary 9. Let p be a prime number. Then there are exactly ø(p–1) many incongruent integers
of order p – 1 modulo p; that is, there are exactly ø(p – 1) many primitive roots (mod p).
Lemma 10. Let p >1 be a prime number and let a > 1. Then
$(p*) = pª – pª=1 = p° ( 1 –
Theorem 11. Let a, b, n E Z. If n and a are relatively prime and n| (ab), then n|b.
Theorem 12. Let a, b, n be integers where a |n and b|n. If (a, b) = 1, then (ab) |n.
Lemma 13 (Euclid's Lemma). Let a and b be natural numbers and let p be a prime. If p|(ab),
then p|a or p|b.
Corollary 14. Let a be a natural number and p be a prime. If p|a², then p|a.
Theorem 15. Let a, r, m be integers. Then (a, m) = 1 and (r, m) = 1 if and only if (ar, m) = 1.
Theorem 16. Let a, b, m be integers where m > 1. Suppose that the congruence a = b (mod m)
holds. Then (a, m) = 1 if and only if (b, m) = 1.
Corollary 17. Let a, x, b, m be integers where m > 1. If (b, m) = 1 and ax = b (mod m), then
(а, т) — 1 and (х, m) — 1.
Transcribed Image Text:Theorem 1. Let x, y, z be positive integers where x is odd and y is even. Then x, y, z is a primitive Pythagorean triple if and only if there are positive integers u and v such that v², y= 2uv, z = u? + v? (1) where (u, v) = 1, u > v and exactly one of u and v is even. Theorem 2 (Euler's Theorem). Let m be a natural number and let a be an integer such that (a, m) = 1. Then aº(m) = 1 (mod m). Theorem 3. Let m e N and let a € Z be such that (a, m) = 1. Let n be a natural number. Then a" = 1 (mod m) if and only if om(a) |n. (a, b). If d{ c, then the Theorem 4. Suppose that a and b are non-zero integers and let d = equation ax + by = c (2) does not have any integer solutions. If d|c, then this equation has an infinite number of solutions. In fact, if ro and yo is one integer solution to equation (2), then all such solutions have the form x = xo +t a y = Yo – t where t varies over the integers. Definition 5. Let m e N and let a e Z be such that (a, m) = 1. The order (mod m) of a, denoted by om(@), is the least d e N such that ad = 1 (mod m). Definition 6. Let m be a natural number and let a be an integer such that (a, m) Om (a) = 0(m), then a is said to be a primitive root (mod m). = 1. If Corollary 7. Let m e N. If a primitive root (mod m) exists, then there are exactly o(0(m)) incongruent primitive roots (mod m). Theorem 8. Let p be a prime number and let d e N be such that d|(p – 1). Then there are exactly ø(d) many incongruent integers of order d modulo p. Corollary 9. Let p be a prime number. Then there are exactly ø(p–1) many incongruent integers of order p – 1 modulo p; that is, there are exactly ø(p – 1) many primitive roots (mod p). Lemma 10. Let p >1 be a prime number and let a > 1. Then $(p*) = pª – pª=1 = p° ( 1 – Theorem 11. Let a, b, n E Z. If n and a are relatively prime and n| (ab), then n|b. Theorem 12. Let a, b, n be integers where a |n and b|n. If (a, b) = 1, then (ab) |n. Lemma 13 (Euclid's Lemma). Let a and b be natural numbers and let p be a prime. If p|(ab), then p|a or p|b. Corollary 14. Let a be a natural number and p be a prime. If p|a², then p|a. Theorem 15. Let a, r, m be integers. Then (a, m) = 1 and (r, m) = 1 if and only if (ar, m) = 1. Theorem 16. Let a, b, m be integers where m > 1. Suppose that the congruence a = b (mod m) holds. Then (a, m) = 1 if and only if (b, m) = 1. Corollary 17. Let a, x, b, m be integers where m > 1. If (b, m) = 1 and ax = b (mod m), then (а, т) — 1 and (х, m) — 1.
Let m e N and a e Z. Suppose that 3|o(m) and that a is a
primitive root (mod m). Prove that a is not a primitive root (mod m).
[You must clearly write and justify
steps in your proof.]
Transcribed Image Text:Let m e N and a e Z. Suppose that 3|o(m) and that a is a primitive root (mod m). Prove that a is not a primitive root (mod m). [You must clearly write and justify steps in your proof.]
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps with 2 images

Blurred answer
Knowledge Booster
Finite State Machine
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, advanced-math and related others by exploring similar questions and additional content below.
Similar questions
  • SEE MORE QUESTIONS
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,