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.