Understanding Residue Systems and Euler's Phi Function in Mathematics
Residue Systems, also known as Reduced Residue Systems, play a significant role in number theory. They involve concepts like the Euler Phi Function, which counts integers relatively prime to a given number. Complete Residue Systems and their properties are explored, highlighting the least non-negative residue of integers modulo m. Examples and explanations help clarify these fundamental mathematical concepts.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
RESIDUE SYSTEMS RESIDUE SYSTEMS (MOD M) (MOD M) Presented By:- Mrs. Shalini Assistant Professor in Maths
EULER PHI FUNCTION Euler Phi Function [ (n)] is the number of non- negative integers less than n that are relatively prime to n and (1)=1. In other words, (n) is the number of m N such that 1 m<n and gcd(m,n)=1. For example, (2)=1, (4)=2, (12)=4, (15)=8 and (p)=p 1.
Least Non-negative Residue of a (Mod m) Let a, b and m( 0) be any integers such that a b (mod m) Then b is a residue of a modulo m. Thus, Residue is another word meaning remainder, and is any integer congruent to a modulo m. The smallest (non-negative) integer congruent to a modulo m is called Least non- negative residue of a(mod m). Or in other words, Let m N. Given any integer n, the least nonnegative residue of n modulo m is the unique integer r such that n r mod m and 0 r < m; i.e., r is the remainder upon division of n by m by the division algorithm.
EXAMPLE Find the least residue of 33 modulo 7. Solution: Find the quotient and remainder when you divide 33 by 7. To do this, first notice that 5 < 33/7 < 4, so the quotient is 5. The remainder is then given by a qn. Since 33 = 7 ( 5) + 2, the least residue is 2.
COMPLETE RESIDUE SYSTEM(CRS) Definitions: 1.A set of numbers a0,a1, , am-1(mod m ) form a complete set of residues, if they satisfy ai i(mod m) for i= 1,2, ., m-1. 2. A Complete residue system modulo m is a set of m integers which satisfy the following condition: Every integer is congruent to a unique member of the set modulo .
COMPLETE RESIDUE SYSTEM(CRS) (Continued) Examples: {1,2,3},{4,5,6} ,{9,17,85} and are all Complete residue systems (mod 3). {4,-7,14,7} is a Complete residue systems (mod 4). {12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23} is a CRS (mod 12) which is equivalent to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. Any consecutive string of m integers forms a complete residue system (mod m).
REDUCED RESIDUE SYSTEMS MOD M A subset R of the set of integers is called a reduced residue system modulo m if i. no two elements of R are congruent modulo m, ii. gcd(r,m)=1} for each r R, iii. R contains (m) elements, A reduced residue system modulo m can be formed from a complete residue system modulo m by removing all integers not relatively prime to m.
REDUCED RESIDUE SYSTEMS MOD M For example, a complete residue system modulo 12 is {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. 1, 5, 7 and 11 are the only integers in this set which are relatively prime to 12, and so the corresponding reduced residue system modulo 12 is {1, 5, 7, 11}. Note that the cardinality of this set is (12)=4. Some other reduced residue systems modulo 12 are {13, 17, 19, 23} and { 11, 7, 5, 1}.
EXERCISE Q1. Show that the following sets form CRS: {5,-3,-4,7,12,22} (mod6) Solution : The least residues of 5 is 5, -3 is 3, -4 is 2, 7 is 1, 12 is 0 and 22 is 4. Which is the set {0,1,2,3,4,5}, hence the given set forms a CRS (mod6). Q2. Show that integers -31, -16,-8,13,25,80 form a RRS (mod 9). Solution: The least residues are: 5,2,1,4,7,8 Note that all are less than 9 and relatively prime to 9 and also incongurent (mod9). Also, we can easily see that (9) = 6 and these 6 integers are 1,2,4,5,7,8 Since this set is equal to set of least residues therefor the given set forms RRS (mod 9).
Q3. If m is an odd positive integer , show that {-(m- 1)/2, -(m-3)/2, ., -1,0,1, ..,(m-3)/2,(m-1)/2} is a CRS (mod m). Solution: -(m-1)/2 (m+1)/2 (mod m) -(m-3)/2 (m+3)/2 (mod m) .. -2 m-2 (mod m) -1 m-1 (mod m) 0 0(mod m) 1 1 (mod m)
. . (m-1)/2 (m-1)/2 (mod m) Thus least residues of given set of integers are 0,1,2,3 ..,m-1/2,m+1/2, ..,m-2,m-1. Thus it is CRS (mod m). Q4. show that 12, 22, ,m2 is not CRS (mod m) if m>2. Solution:let a= 12and b = (m-1)2. Then a-b= 2m - m2and thus a-b 0 (mod m) i.e. a b (mod m). Thus the set is not CRS (mod m)
