Linear Algebra - Cryptography (PROBLEM FROM Elementary Linear Algebra Applicatio
ID: 3147883 • Letter: L
Question
Linear Algebra - Cryptography (PROBLEM FROM Elementary Linear Algebra Application Version Edition 11th Howard Anton Chris Rorres) --- Chapter 10 Section 14 (T2)
Given a positive integer n greater than 1, the nuber of posotive integers less than n and relatively prime to n is called the Euler phi function of n and is denoted by (n) for example, (6)=2 since only two positive integers (1 and 5) are less thn 6 and have no common factor with 6.
a). Using a computer (using MatLab), for each value of n =2,3,....25 comute and print out all posotive integers that are les than n and relatively prime to n. Then use these integers to determine the values of (n) for n=2,3,......25. Can you discover a pattern in the results?
b). It can be show that if (p1, p2, p3, ........ pm) are all distinct prime factors of n, then (n)=n(1-(1/p1))(1-(1/p2))(1-(1/p3))......(1-(1/pm)) for example since (2,3) are distinct prime factors of 12, we have (12)=12(1-(1/2))(1-(1/3))=4
which agrees with the fact that (1,5,7,11) are the only positive integers less than 12 and relatively prime to 12. Using a computer (MatLab), print out all the prime factors of n for n=2,3.....25. Then compute (n) using the formula above and compare it to your results in part (a).
Explanation / Answer
Number Number Less than but prime to n Numbers that are prime factors value of phi
2 1 2 1
3 1 2 3 1
4 1,2 2 2
5 1,23,4 5 4
6 1,5 2,3, 2
7 1,2...6 7 6
8 1 3 5 7 2 4
9 1 2 4 5 7 8 3 6
10 1 3 7 9 2 5 4
11 1...10 11 10
12 15 7 11 2 3 4
13 1...12 13 12
14 1, 3, 5, 9,11,13 2 7 6
15 1 2 4 6 7 8 11 13 14 3 5 8
16 1 3 5 7 9 11 13 15 2 8
17 1...16 17 16
18 1 5 7 11 13 17 2 3 6
19 1...18 19 18
20 1 3 7 9 11 13 17 19 2 5 8
21 12 4 5 8 10 11 13 16 17 19 20 3 7 12
22 1 3 5 7 9 13 15 17 19 21 2 11 10
23 1...22 23 22
24 1 , 5 7 11 13 17 19 23 2 3 8
25 1 2 3 4 6 8 9 11 12 13 14 16 17 18 19 5 20
21 22 24 23
A) Thus we can see a pattern that all the Phi values are Even.
B) Also it can be Verified that Formula described for Phi (n) is true for each of
the number in the table.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.