Exercise 5. (a) Use Proposition 3.5.20 to prove the following: if k> integer m with 0 ≤ m < N then there exists an integer will need the fact that N = 1. 3 0 and k is relatively prime to N, then for any such that (k)= m. (To do this problem, you (b) Show that I found in the previous exercise can be chosen between 0 and N - 1. (c) Show that if k> 0 is relatively prime to N, then the complex numbers (k), j = 0,... N - 1 are exactly the Nth roots of unity in rearranged order.(Hint: show that according to the previous exercise, all N of the Nth roots of unity are included somewhere among these N numbers. So all N numbers are accounted for.)
Exercise 5. (a) Use Proposition 3.5.20 to prove the following: if k> integer m with 0 ≤ m < N then there exists an integer will need the fact that N = 1. 3 0 and k is relatively prime to N, then for any such that (k)= m. (To do this problem, you (b) Show that I found in the previous exercise can be chosen between 0 and N - 1. (c) Show that if k> 0 is relatively prime to N, then the complex numbers (k), j = 0,... N - 1 are exactly the Nth roots of unity in rearranged order.(Hint: show that according to the previous exercise, all N of the Nth roots of unity are included somewhere among these N numbers. So all N numbers are accounted for.)
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Question
Please do Exercise 5 part A-D and please show step by step and explain
Transcribed Image Text:From Proposition 3.5.20 in the book we have: “Given a modular equation \(kx \equiv m \pmod{N}\), where \(k, m, N\) are integers. Then the equation has an integer solution for \(x\) if and only if \(m\) is an integer multiple of the greatest common divisor of \(k\) and \(N\.”
**Exercise 5.**
(a) Use Proposition 3.5.20 to prove the following: if \(k > 0\) and \(k\) is relatively prime to \(N\), then for any integer \(m\) with \(0 \leq m < N\) there exists an integer \(\ell\) such that \((\zeta^k)^\ell = \zeta^m\). (To do this problem, you will need the fact that \(\zeta^N = 1\).)
(b) Show that \(\ell\) found in the previous exercise can be chosen between 0 and \(N - 1\).
(c) Show that if \(k > 0\) is relatively prime to \(N\), then the complex numbers \((\zeta^k)^j, j = 0, \ldots, N - 1\) are exactly the \(N\)th roots of unity in rearranged order. (*Hint: show that according to the previous exercise, all \(N\) of the \(N\)th roots of unity are included somewhere among these \(N\) numbers. So all \(N\) numbers are accounted for.*)
(d) Show that if \(k\) is relatively prime to \(N\), then the sum \(\sum_{j = 0}^{N - 1} e^{2\pi ijk/N}\) is equal to 0.
(e) Now suppose \(0 < k < N\) is not relatively prime to \(N\). Then show that there is a number \(N'\) which divides \(N\) such that \(\sum_{j = 0}^{N - 1} e^{2\pi ijk/N} = 0\). Show also that \(\sum_{j = 0}^{N' - 1} e^{2\pi ijk/N} = 0\) by breaking this sum of \(N\) terms into
Expert Solution
Step 1
Step by step
Solved in 2 steps with 3 images
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
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…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
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…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
