Euler's Theorem

Definition (Euler's φ-Function) For each integer euler theorem _gr_1.gif] let euler theorem _gr_2.gif] denote the number of positive integers less than euler theorem _gr_3.gif] and relatively prime to euler theorem _gr_4.gif] and let euler theorem _gr_5.gif] The function euler theorem _gr_6.gif] is called the Euler's euler theorem _gr_7.gif]-function, or sometimes the totient function.

Definition (Reduced Residue System) A reduced residue system modulo n is a set of euler theorem _gr_8.gif] integers such that each element of the set is relatively prime to euler theorem _gr_9.gif] and no two different elements of the set are congruent modulo euler theorem _gr_10.gif]

Example (Reduced Residue System) Find a reduced reside system modulo, 13, 12, and 28. Also find three distinct sets which are all reduced residue systems modulo 28.

    Solution. The set euler theorem _gr_11.gif] is a reduced residue system modulo 13. The set euler theorem _gr_12.gif] is a reduced residue system modulo 12. The set

euler theorem _gr_13.gif]

is a reduced residue system modulo 28. The set

euler theorem _gr_14.gif]

is also a reduced residue set modulo 28. Finally, the set

euler theorem _gr_15.gif]

is also a reduced residue set modulo 28. euler theorem _gr_16.gif]

Proposition (Reduced Residue System) If euler theorem _gr_17.gif] is a reduced residue system modulo euler theorem _gr_18.gif] and euler theorem _gr_19.gif] then euler theorem _gr_20.gif] is also a reduced residue system modulo euler theorem _gr_21.gif] Moreover, the numbers euler theorem _gr_22.gif] are congruent to the numbers euler theorem _gr_23.gif] modulo euler theorem _gr_24.gif] in some order.   

    Proof. We need to show that euler theorem _gr_25.gif] for each euler theorem _gr_26.gif] and euler theorem _gr_27.gif] for all euler theorem _gr_28.gif] If euler theorem _gr_29.gif] and euler theorem _gr_30.gif] then euler theorem _gr_31.gif] because euler theorem _gr_32.gif] But   euler theorem _gr_33.gif] can not happen because euler theorem _gr_34.gif] is a reduced residue system modulo euler theorem _gr_35.gif]. Suppose euler theorem _gr_36.gif]and that euler theorem _gr_37.gif] is a prime divisor of euler theorem _gr_38.gif] Since euler theorem _gr_39.gif] we can not have euler theorem _gr_40.gif] because euler theorem _gr_41.gif] Therefore, euler theorem _gr_42.gif] and euler theorem _gr_43.gif] By Euclid's lemma euler theorem _gr_44.gif] Clearly, euler theorem _gr_45.gif] and euler theorem _gr_46.gif] contradict euler theorem _gr_47.gif] and so there is no prime divisor of euler theorem _gr_48.gif] for any   euler theorem _gr_49.gif] Therefore, euler theorem _gr_50.gif] is also a reduced residue system modulo euler theorem _gr_51.gif]    euler theorem _gr_52.gif]  

Proposition (Euler's Theorem) If euler theorem _gr_53.gif] then euler theorem _gr_54.gif]

    Proof. Let   euler theorem _gr_55.gif] denote the reduced residue system modulo euler theorem _gr_56.gif] consisting of positive integers not less than euler theorem _gr_57.gif] We know that   euler theorem _gr_58.gif] is also a reduced residue system modulo euler theorem _gr_59.gif] Moreover, the numbers euler theorem _gr_60.gif] are congruent to the numbers euler theorem _gr_61.gif] modulo euler theorem _gr_62.gif] in some order. So

euler theorem _gr_63.gif]
    
Since euler theorem _gr_64.gif] we divide by euler theorem _gr_65.gif] to obtain

euler theorem _gr_66.gif]
euler theorem _gr_67.gif]    

Example (Euler's Theorem) Show that euler theorem _gr_68.gif]

    Solution. A reduced residue system modulo 16 is

euler theorem _gr_69.gif]

and so is

euler theorem _gr_70.gif]

Therefore, they have the same least positive residue modulo 16. Hence,

euler theorem _gr_71.gif]

Since euler theorem _gr_72.gif] we divide by euler theorem _gr_73.gif] to obtain

euler theorem _gr_74.gif]
euler theorem _gr_75.gif]

Proposition (Euler's Theorem Solves Linear Congruence Equation) The solution to the linear congruence euler theorem _gr_76.gif] is euler theorem _gr_77.gif] provided euler theorem _gr_78.gif]

    Proof. If euler theorem _gr_79.gif] then by Euler's theorem euler theorem _gr_80.gif] and so multiplying by euler theorem _gr_81.gif] we have euler theorem _gr_82.gif] and so euler theorem _gr_83.gif] is a solution. euler theorem _gr_84.gif]
    

Example (Euler's Theorem Solves Linear Congruence Equation) Solve the linear congruence euler theorem _gr_85.gif]

    Solution. The solution is euler theorem _gr_86.gif] where euler theorem _gr_87.gif] euler theorem _gr_88.gif] euler theorem _gr_89.gif] and euler theorem _gr_90.gif]. Thus,

euler theorem _gr_91.gif]
euler theorem _gr_92.gif]

Example (Finding Digits with Euler's Theorem) Find the last digit of the decimal expansion of euler theorem _gr_93.gif]

    Solution. Since euler theorem _gr_94.gif] and euler theorem _gr_95.gif] by Euler's Theorem we have,

euler theorem _gr_96.gif].

So the last digit in the expansion of euler theorem _gr_97.gif] is 1 and thus the last digit in the expansion of euler theorem _gr_98.gif] is of course 2.
    Since euler theorem _gr_99.gif] and euler theorem _gr_100.gif] by Euler's Theorem we have,

euler theorem _gr_101.gif].

So the last digit in the expansion of euler theorem _gr_102.gif] is 7 and thus the last digit in the expansion of euler theorem _gr_103.gif] is of course 9. Since the sum of integers with last digit of 2 and last digit of 9 is 1, the last digit of euler theorem _gr_104.gif] is a 1. euler theorem _gr_105.gif]

Cite this as:
Euler Theorem
Published by Library of Math -- Online math organized by subject into topics.
Written by Smith, David A.
http://www.libraryofmath.com/euler-theorem.html
 
    
Library of Math
Library of Math
Online Math Organized by Subject Into Topics
math search
Library of Math AddThis Feed Button
Online Math
Math Books
Custom math gifts on sale now.
Share your enthusiasm for mathematics!
Famous Theorems
Math Gifts
The Library of Math - Online Math Organized by Subject Into Topics.
© 2005 - 2008 www.LibraryOfMath.com All rights reserved.
about us | feedback | privacy policy | terms of use | mision statement | help

Page copy protected against web site content infringement by Copyscape Valid CSS! Valid HTML 4.01 Transitional Subscribe to the Library of Math Feed
Art & Photography Shop | Being Healthy Shop | Best Sports Mall | Cafe Food Lover | Cafe Gift Shop | Cafe Internet Shop | Career Archives | City Annals
Countries Shop | Crazy Kids World | Dallas Cowboys Football Shop | Headline News Shop | Heart Boutique | Lover of Pets | Military Support Store
Musical Boutique | Online Math Store | Political Ramblings | Shop by Auction | Shop of Learning | Shop of Technology | Shop of Travels | Special Occasion Shop
Store of Hobbies | Theology Store | USA States Shop | Your Animal Store | Your Fitness World | Your Funny Store | Your Science Store