### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# ELEM NUMBER THEORY MATH 780

GPA 3.51

### View Full Document

## 21

## 0

## Popular in Course

## Popular in Mathematics (M)

This 18 page Class Notes was uploaded by Cassidy Grimes on Monday October 26, 2015. The Class Notes belongs to MATH 780 at University of South Carolina - Columbia taught by Staff in Fall. Since its upload, it has received 21 views. For similar materials see /class/229546/math-780-university-of-south-carolina-columbia in Mathematics (M) at University of South Carolina - Columbia.

## Reviews for ELEM NUMBER THEORY

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15

Math 780 Elementary Number Theory Instructor s Notes What Is It 0 Elementary Number Theory is the study of numbers and in particular the study of the set of positive integers 0 Does elementary mean easy No 0 Example Consider a positive integer m lt 105 and view it as a four digit number with possible leading digit 0 Suppose all four digits are distinct Let k be the number obtained by putting the digits of m in increasing order and let 6 be the number obtained by putting the digits in decreasing order Let m k 6 Now repeat the process with m in place of m Continue What happens How can this be explained Rational and Irrational Numbers 0 De ne them 0 Theorem 1 is irrational 0 Give typical proof 0 Theorem 2 An irrational number to an irrational power can be rational 5 0 Proof Consider and 0 Theorem 3 e is irrational 0 Proof Assume e a b with a and 6 positive integers and set b b b 9 666 237 Z j0 jb1 Then 1 1 0 lt 6 lt lt 1 321 6 1 b On the other hand the middle expression in is an integer Hence we have a contra diction and e is irrational 0 Open Problem ls 7rE irrational 1 0 Open Problem ls Z 75 irrational n 711 These notes are from a course taught by Michael Filaseta in the Fall of 1997 2 Homework 1 Let I R denote the set of irrational numbers Determine whether each of the following is true or false If it is true simply state so If it is false state so and give a counterexample a aEIand36Iimpliesa3 I b a E I and 3 E I implies 13 E I c aEQ O and36Iimpliesa3 Ianda3 I d a E I and 3 E Q 0 implies 03 E I e a E Q 1 and 3 E I implies 03 E I 2 Prove that is irrational whenever n is a positive integer which is not a square Give an argument similar to that given for Clarify where you feel we are using certain properties of the integers that we should have perhaps discussed rst Prove that is irrational 4 Prove that is irrational 5 Prove that log 3 is irrational 6 Prove that 82 is irrational using an argument similar to that given above for e Divisibility Basics 0 De nition Let a and b be integers Then a divides b or a is a divisor of b or b is divisible by a if there is an integer c such that b 2 ac 0 Notation We write ab if a divides b and we write af 6 if a does not divide b 0 De nition An integer p is prime or is a prime if it is gt 1 and divisible by no other positive integer other than 1 and itself In Algebra the condition that p be gt 1 is replaced by gt 1 o The division algorithm Theorem 4 Ifa 7 2 0 and b are any integers then there exist unique integers 1 called the quotient and r called the remainder with 0 g r lt a such that b qa r 0 Proof Let r be the least non negative integer in the double sequence b 2ab abbab2a Let 1 be such that b qa r Since 6 qa a is in the double sequence and lt b qa we have b qa a lt 0 Thus r lt a Also r 2 0 This proves the existence of q and r as in the theorem For j 6 12 suppose qj and rj are integers such that b qja rj and 0 g rj lt a Then l 91 QQla 7 1 7 2 0 This implies arl rg On the other hand rl r2 6 a a Hence rl rg Now implies 11 12 establishing the uniqueness of q and r as in the theorem 3 0 De nition and Notation Let n and m be integers with at least one non zero The greatest common divisor of n and m is the greatest integer dividing hoth n and m We denote it by gcdnm or n 0 Note that if n is a non zero integer then 0 n n 0 Theorem 5 Ifa and b are integers with at least one nonzero then there exist integers x0 and ya such that axo byo a b Moreover axbyxy ZkabzkEZZ 0 Proof Let S axby x y E Let d denote the smallest positive integer in S Let x0 and ya he integers for which at axo byo Theorem 5 follows from the following claims Claim 1 hot k E C S Reason Clear Claim 2 S C kdz k E Reason Let u ax by E S By Theorem 4 we have integers q and r with u dq r and 0 g r lt d On the other hand r u dq ax39 by39 axe byoq a2039 xoq 63 3m 6 S It follows that r 0 and u 2 got Claim 3 da and db Reason Use Claim 2 together with a E S and b E S Claim 4 d a 6 Reason Since axo byo d abd so that a b g d Since da and db dis a common divisor of a and b By the de nition of greatest common divisor d 2 ab The Fundamental Theorem of Arithmetic Unique Factorization 0 Theorem 6 Every integer n gt 1 can be written uniquely as a product ofprimes in the form n pi where p1 lt p2 lt lt p are distinct primes and 8182 er and r are positive integers 0 Comment In other words every positive integer n can be written uniquely as a product of primes except for the order in which the prime factors occur 0 Lemma pr is a prime and a and b are integers such that pab then either pa or pb 0 Proof of Lemma Let k be an integer such that ab 2 hp and suppose p f a We wish to show pb By Theorem 5 there are integers x and y such that am pg 2 1 Hence 6 abx pby pkx by Thus pb 0 Proof of Theorem 6 First we prove that n is a product of primes by induction The case n 2 is clear Suppose it is true for n less than some integer m gt 2 If m is prime then m is a product of primes If m is not prime then m ab with a and b integers in 1 Since a and b are products of primes by the induction hypothesis so is m Now we prove uniqueness by induction Again one checks n 2 directly Suppose uniqueness of the representation of n as a product of primes as in the theorem holds for n lt m Let p1 pr not necessarily distinct and 11 1 not necessarily distinct denote primes such that m 2 p1 pr 2 11 1 Observe that p1q1 qt Hence the lemma implies p1q1 or p1q2 1 This in turn implies p1q1 p2q2 or p1q3 1 Continuing we deduce that p1qj for some j 6 12 t As p1 and qj are primes we obtain p1 qj Now p2 p mp1 11 qj1qj1 1 and the induction hypothesis imply that the primes p2 pr are the same as the primes 11 Qj i 1j1 1 in some order This implies the theorem Homework 1 Let a b c and d denote positive integers Prove each of the following a ab and bc implies ac b acbc implies ab c ab and cd implies acbd 2 Prove that if n is an integer 2 2 which is composite ie not prime then n has a prime divisor which is g 3 Let S 2 lo 39 39 rime Prove that the elements of S are linearl r inde endent E1017 P P 3 P over the rationals This is an example of an in nite set of real numbers which is linearly independent over 4 Observe that n 1 4quot is prime if n 1 Prove that n 1 4quot is composite if n is an integer gt 1 Euclidean Algorithm 0 Review In grade school we learned to compute the greatest common divisor of two numbers by factoring the numbers For example 77 119 7 X 11 7 X 17 7 Now try 3073531304313 this way VVhat s the moral 0 Theorem 7 The Euclidean Algorithm Leta and b be positive integers Set 7 0 2 a and 71 6 De ne 712713 rn and n by the equations 7 0 2 rlql 712 with 0 lt 7 2 lt 71 7 1 7 2q2 73 with 0 lt 713 lt 742 7 n2 7n1qn1 Tn with 0 lt Tn lt 7n1 Til 1 7 an n1 with n1 0 where each qj and rj is in Then a b 7 5 0 Back to examples Compute 3073531304313 this way Not to be misleading compute 2117 3219 using the Euclidean Algorithm 0 Proof Let d 16 Then one obtains d73 for 0 g j g n1 inductively and hence d7 n Thus at g 731 since 7 gt 0 Similarly one obtains 731 divides 7 nj for 1 g j g 71 It follows that 731 is a divisor of a and b By the de nition of 16 we deduce 731 a b 0 Solutions to am 63 2 7n From Theorem 5 we need only consider 7n ka 6 One can nd solutions when k 1 by making use of the Euclidean Algorithm backwards Show how the complete set of solutions for general 7n can be obtained from this Also mention the connection with the simple continued fraction for ab 0 Example Solve 321930 21173 29 The solutions are the x y of the form 211 21 x225 tX2 9 and y 38tx fortEZZ 0 Theorem 8 Leta and b be positive integers The Euclidean Algorithm for calcu lating ab takes g 2log2 b 1 steps ie divisions 0 Proof Let s log2 b 1 In the notation of Theorem 7 we want n g 25 Assume n 2 2s 1 We show rst that 732 lt 732 for j 6 12 n 2 If 731 g 732 then 732 lt 731 g 732 If 731 gt 732 then 73 731qj1 732 where qj1 1 Hence in this case 732 73 731 lt 732 Hence in either case 732 lt 732 We deduce that 7171 2 7171 4 7171 25 711 b 1ltr1nlt7lt7ltmlt7lt77 39 2 4 28 8 28 Therefore 5 lt log 6 This contradicts that s log 6 1 gt log 6 Homework 1 For each of the following calculate a b and nd a pair of integers x and y for which ax by 16 a a 289 and b 1003 b a 3569 and b 1333 2 Find the complete set of integer solutions in x and y to 82120 19973 24047 Modulo Arithmetic 0 De nition Two integers a and b are congruent modulo an integer n if na b 0 Notation a E 6 mod 71 0 Examples What will be the time 1000 hours from now On what day of the week will September 3 be in 1998 0 Theorem 9 Leta b c and n be integers Then each of the following holds i1fa E b mod n and b E c mod n then a E c mod n ii1fa E b mod n and c E d mod n then a c E b d mod n iii fa E b mod n and c E d mod n then ac 2 bd mod n 711 fa E b mod n and dn then a E b mod d 0 Proof Give the obvious proofs In particular in iii observe that a b 2 kn and c d 2 Zn for some integers k and 6 so that ac bot a bc c db kc tbn and the result follows 0 Comment Note that iii implies that if a E b mod n and k is a positive integer then ah E bk mod n 0 Theorem 10 Let m be a positive integer and let a be an integer relatively prime to m Then there is an integer x for which am 2 1 mod 0 Proof Use that there are integers x and y such that am my 2 1 0 Comments The x in Theorem 10 is called the inverse of a modulo m It is unique modulo m since a m 1 and am 2 big mod m implies x E y mod Also note that if am 7 2 1 then a does not have an inverse modulo m since ax 1 2 ml would be impossible 0 Examples Explain the usual tests for divisibility by each of 2 3 4 5 6 9 and 11 2 What is the last digit of 71000 23 Determine the last digits of the numbers in the sequence 23 2323 2323 l gt gt 1 H 3 4 Is 3752743877345287574827904870128487127731 a sum of two squares 5 Let F 2m 1 the nth Fermat number Explain why 641F5 Use that 64 2 15 1 and6415gtlt271 0 Comments A regular n gon is constructible with straight edge and compass if and only if n 2kp1 pr 2 3 where k and r are non negative integers and p1 pr are distinct Fermat primes The only known Fermat primes are F for 0 g n g 4 ie 3 5 17 257 and 65537 and it is believed that these are the only Fermat primes Homework 1 Prove that if n E 7 mod 8 then n is not a sum of 3 squares 2 Prove that for every non constant polynomial f with integer coef cients there is an integer m such that is composite A large furniture store sells 6 kinds of dining room suites whose prices are 231 273 429 60060 1001 and 150150 respectively Once a South American buyer came purchased some suites paid the total amount due 1351990 and sailed for South America The manager lost the duplicate bill of sale and had no other memorandum of each kind of suite purchased Help him by determining the exact number of suites of 7 each kind the South American buyer bought Don t forget to show that your solution is unique 4 Find with proof the smallest integer gt 1 dividing at least one number in the sequence 31 331 3331 33331 Fermat s Little Theorem 0 Theorem 11 For any prime p and any integer 1 ap a is divisible by p 0 Comments In other words with p and a as above ap E a mod p The theorem is equivalent to if p is a prime and a is an integer with a p 1 in other words with p not dividing a then ap1 2 mod p 0 Proof 1 Use induction The theorem holds with a 1 If it holds for a then 10 v a1pZ aJEap1Ea1 modp i0 This proves the theorem for positive integers Since every integer is congruent to a positive integer modulo p the result follows 0 Proof 2 Again we may suppose a gt 0 Fix 1 colors The number of necklaces with p beads each bead colored with one of the 1 colors allowing repetitions having at least two beads colored differently is ap a p Here we count necklaces as distinct if one cannot be obtained from the other by a rotation we don t allow ipping necklaces over Thus ap a p E and the result follows 0 Fermat s Little Theorem can be used for determining that a given integer N is composite as follows i Check N for small prime factors this step isn t necessary but is reasonable ii Write N in base 2 say N 2310 ij with 6339 E 0 1 for each j and k log N log 2 1 iii Compute 22 mod N by squaring iv Calculate m E 0 1 N 1 such that k m E H 25139 E 2N mod N i0 v If m 7 2 2 then N is composite Otherwise the test is inconclusive 0 Comments The algorithm works for establishing that most composite numbers are composite ie for most composite numbers m 7 2 2 If m 2 then one can check if 3N E mod N Note that the algorithm takes on the order of log N steps so that the algorithm is a polynomial time algorithm it runs in time that is polynomial in the length of the input elaborate on this There are no polynomial time algorithms that determine conclusively whether an arbitrary integer is composite 0 De nitions A pseudoprime is a composite number n gt 1 satisfying 2quot E 2 mod n A probable prime is an integer n gt 1 satisfying 2quot E 2 mod n Explain the reasons behind these de nitions 0 Examples Explain why 341 11 X 31 is a pseudo prime Explain why F 227 1 is a probable prime Note that for n gt 5 F is really probably not a prime 0 De nition An absolute pseudoprime or a Carmichael number is a composite number n gt 1 such that aquot E a mod n for every integer a 0 Example Explain why 561 3 X 11 X 17 is an absolute pseudo prime 0 Comment Alford Granville and Pomerance have shown that there exist in nitely many absolute pseudo primes The much easier result that there exist in nitely many pseudo primes is in the next list of homework problems Euler s Theorem 0 De nition and Notation For a positive integer n we de ne n to be the number of positive integers g n which are relatively prime to n The function I is called Euler s it function 0 Examples 1 1 1 2 4 2 p 1 for every prime p and pq p 1q 1 for all primes p and q 0 Theorem 12 For every positive integer n and every integer a relatively prime to n we have a i m E 1 mod n 0 Proof If n 1 the result is clear We suppose as we may then that n gt 1 Let a1a2 awn be the n positive integers g n relatively prime to n Consider the numbers alaa2aa na Note that no two numbers in are congruent modulo n since an 1 and aia E aja mod n implies ai E aj mod n so that i j Now x j 6 12 n There are integers q and r such that aja nq r and 0 g r lt n Since ajan 1 and n gt 1 we obtain r 7 2 0 and r n 1 Thus r ah for some I 6 12 n Hence for each j E 12 n there is a k E 12 n for which aj E ah mod n Since the numbers aja are distinct modulo n we deduce that the numbers in are precisely a1 a2 aw in some order Therefore a1a2a n E alaa2a a ma E a quota1a2 a n mod n Since gcda1a2 awn n 1 we obtain a i m E 1 mod n as desired Wilson s Theorem 0 Theorem 13 For every prime p p 1 E 1 mod p 0 Proof Up 2 the result is clear We consider now the case p gt 2 Let S 12 p 1 For every a E S there is a unique a E S satisfying a a E 1 mod p 9 If a 1 or a p 1 then a a The converse statement also holds since a 1 implies a 1a 1 a2 1 is divisible by p so that a E 1 mod p or a E p 1 mod p The remaining elements of S can be grouped in p pairs aa say 11 1 1 ap32 aEp32 so that p 1 E 1 x p 1 x a1a1ap32ap32 E 1 x p 1 E 1 mod p 0 Comment The converse of W ilson s Theorem also holds see homework problem 4 below Homework 1 Prove that 1105 and 1729 are absolute pseudo primes 2 Prove that if n is a pseudo prime then 2quot 1 is a pseudo prime Note that this implies that there are in nitely many pseudo primes Find the smallest positive integer k such that ah E 1 mod 756 for every integer a which is relatively prime to 756 4 Prove the converse of W ilson s Theorem More speci cally prove that if n is an integer gt 1 for which n 1 E 1 mod n then n is a prime 5 Let p and d be integers with p gt 1 and d gt 0 Prove that p and p d are both prime if and only if 1 1ddl 1 1 r 1 7 77 p p pd p pd is an integer PublicKey Encryption 0 Example The following information is made public If someone wishes to send me Jim a message use the following Let N 49601 and s 247 As your alphabet use 00 for a blank 01 for a 02 for b 03 for c etc Eg No would be represented 1415 Suppose your message is 17W Let E Ell5 mod N where 0 g E lt N Then AI is your actual message and E is the encnjpted message Publish E in the personals tomorrow and I alone will know your actual message 17W Note To do this properly one needs N to be considerably larger Here only two letter words can actually be sent though a combination of two letter words including blanks can make for a sentence 0 The secret The number N is a product of two large primes suf ciently large so only Jim knows how N factors In the example above N 193 X 257 Since Jim knows how N factors he can also compute In this case N 193 x 257 192 x 256 49152 10 Using the Euclidean algorithm for example Jim also knows a positive integer t such that st 2 1 mod Here t 199 Thus Jim and only Jim can calculate E 2 Mst 2 MWMH 2 M mod N In other words Jim can gure out NI given the value of E 0 Comment This approach makes for a good public key encryption scheme because the value of N cannot seemingly be computed without the knowledge of how N factors To clarify it is possible to compute N without having the factorization of N but the fastest known methods at the time for computing N when N is large involve rst factoring N 0 Further example Someone has sent the encrypted message E 48791 to Jim What should he do assuming he wants to know what the message says Note that t1992726222r By squaring he computes E E 48791 mod N E2 2 11287 mod N E22 2 21001 mod N E23 2 39510 mod N E24 a 47029 mod N E25 a 18251 mod N E26 a 28286 mod N E27 2 33666 mod N Hence M 2 E 2 E27E26E22E2E1 E 3366628286210011128748791 E 809 mod N The message sent was Hi Homework 1 Someone wants to send Jim the message No Compute the encrypted message E and then verify your work by decoding E Show your work using steps similar to that shown above Certi ed Signatures o The problem Jim has two friends Brian and Jason Jim just got an encrypted message E in the personals I won t specify what E was because it might upset Jim since you can now decode Jim s messages because you too know how N factors The message to Jim in the personals read Jim I really like your idea for having secret messages sent to you so that no one else can know what s being said in the personals besides you In fact I liked it so much that I thought I would send you a quick note to let you know what I think of you Here it is E Sincerely Brian In the above message E is actually some number The problem is that when Jim decoded E he was not very happy about what Brian had to say and you wouldn t be either if you happened to be the one the message E was intended for As a consequence Jim and Brian never talked to each other again and Jim s best friend became Jason What Jim never did gure out though was that Jason actually wrote the message 0 Solution One can sign a message simply by adding ones name to the end of a message 1M and then encrypting the whole message name and all Unfortunately this is precisely what Jason did he added Brian s name to the end of the message sent to Jim When Jim read it he actually thought that Brian must have sent it since no one else could possibly have encrypted Brian s name He never realized that actually anyone could encrypt Brian s name There is however a proper way to certify a signature in an encrypted message Let s suppose that Brian and Jason also decided to use the same encrypting scheme as Jim In particular Brian has some number N that he alone knows how to factor and some number 5 both of which he makes public And suppose he has computed t his secret exponent for decoding messages sent to him satisfying s t E 1 mod N Note that S 0218090114 represents Brian s name Brian computes the value of T E S 5 mod N with 0 g T lt N Since t is only known to Brian T is something only Brian knows If Brian wants to truly sign a message to Jim so that Jim knows it is from him he now simply adds T to the end of his message and then encrypts the entire message with T When Jim receives the message he decodes it To verify the message is from Brian he takes the value of the signature T given at the end of the message and computes Tsl modulo N note that both 5 and N are known to him Since s t E 1 mod N Jim obtains S this way ie S 2 TS mod N He then sees that the message is from Brian The main point is that since t is only known to Brian he alone could have computed the value of T given at the end of the message to Jim 0 The rest of the story Actually Brian did have numbers N and 5 that he made public and Jason had such numbers as well Jason sent a friendly message to Brian which Jason signed with a certi ed signature Brian responded with a message containing his own certi ed signature It was then that Jason sent his message to Jim At that point Brian had given Jason the value of T Brian s certi ed signature so Jason used Brian s certi ed signature in his message to Jim So how might this problem be avoided Discuss possible answers 12 The Chinese Remainder Theorem 0 Theorem 14 Let 7n1mk be pairwise relatively prime positive integers Let b1 bk be arbitrary integers Then the system as 2 b1 mod ml 30 E by mod my has a unique solution modulo m1 mk 0 Proof Constructive Let IV m1mk For j E 12k de ne Aj bImj Ifi andj are in 12k with i 7 2 j then mhmj 1 It follows that for eachj 6 12 k AIj7nj 1 so that there is an E such that bjAIj39v E 1 mod mj We set x 221 bijMJQ Then as E bjAjbIj39v E bj mod mj for j 6 12 This proves the existence of a solution to the system of congruences in the statement of the theorem For uniqueness suppose that y also satis es y E bj mod mj for each j E 1 2 Then y x E 0 mod mj for each such j and we deduce that each mj divides y x As the mj are relatively prime we obtain 1V1 In other words y E 30 mod m1 my 0 Examples 1 Solve 1730 E 3 mod 210 by using the Chinese Remainder Theorem Use that 210 2 X 3 X 5 X 7 and observe that solving 1730 E 3 mod 210 is equivalent to solving the system as E 1 mod 2 x E 0 mod 3 x E 1 mod 5 and x E 1 mod 7 The latter is equivalent to x E 1 mod 14 and x E 9 mod 15 Therefore CElX15X19X14X lE 111299 moleO 2 If a and b are integers then the point a b is called a lattice point A visible lattice point is one for which gcda b 1 it is visible from the origin Prove that there are circles or squares in the plane which are arbitrarily large and have the property that each lattice point in the circles or squares is not visible Use that there are in nitely many primes Prove that there exists a positive integer k for which 2quotk 1 is composite for all positive integers n It is known that k 78557 has this property and it is an open problem to determine whether or not 78557 is the smallest such We use the Fermat 13 numbers F 22n 1 Recall that F is prime for 0 g n g 4 and F5 is composite with 641 a proper divisor Explain the following implications mod 2 gt 2quotk 1 2 mod 4 gt 2quotk 1 2 mod 8 gt 2quotk 1 E 0 mod 17 provided I 2 mod provided I E mod 16 gt 2quotk 1 E 0 mod 257 provided I E 0 0 mod 5 provided I E 6 mod 32 gt 2quotk 1 E 0 mod 65537 provided I E 2 mod 64 gt 2quotk 1 E 0 mod 641 provided I 2 mod 64 gt 2quotk 1 E 0 mod F5641 provided I E 1 2 4 8 1 3 0 7 7 7 7 n n 7 By the Chinese Remainder Theorem there are in nitely many positive integers k satisfying the conditions on k on the right above note that the last modulus is relatively prime to the others Also every integer n can be seen to satisfy at least one of the congruences involving n on the left It follows that there are in nitely many positive integers k such that for every positive integer n the number 27 1 is divisible by one of 3 5 17 257 65537 641 and F5 641 If k is suf ciently large with this property then it will suf ce for a value of k for this example 0 Comments If every integer n satis es at least one of a set of congruences x E aj mod my for j 1 k then the congruences are said to form a covering of the integers It is unkown whether or not there is a covering consisting of distinct odd moduli gt 1 Also it is not known whether or not there is a constant C gt 0 such that every covering using distinct moduli contains a modulus lt C Homework 1 Find the smallest positive integer n gt 2 such that 2 divides n 3 divides n 1 4 divides n 2 5 divides n 3 and 6 divides n 4 Prove your answer is the least such n 2 A squarefree numberis a positive integer n which is not divisible by a square gt 1 For example 1 2 3 5 and 6 are squarefree but 4 8 9 and 12 are not Let k be an arbitrary positive integer Prove that there is a positive integer m such that m 1 m 2 m k are each NOT squarefree Use that there are in nitely many primes Calculate the remainder when the number 123456789101112 19781979 is divided by 1980 4 Let a0 a and a1 b be positive integers and let an 2 2a an1 for all positive integers n Find relatively prime 1 and 6 such that every an with n 2 0 is composite Hint I used the system of congruences n E 0 mod 2 n E 1 mod 3 n E 3 mod 4 n E 5 mod 6 and n E 9 mod 12 You should convince yourselves that this system forms a covering of the integers The idea is to make each an divisible by a prime where the prime depends on which of these congruences n satis es For example suppose I choose a and b so that a E 1 mod and b E 1 mod Then for n satis ng n E 3 mod 4 which is one of the congruences in the system above we will have that an is divisible by 14 3 To see this consider the sequence on modulo 3 keeping in mind that a E 1 mod and b E 1 mod The main problem should be guring out what primes to use Euler s Phi Function Revisited 0 Recall n is the number of positive integers g n that are relatively prime to n 0 Lemma 1 For every prime p and every positive integer k Mpk 2 pk pk1 0 Proof The number of multiples of p which are g pk is pk1 The result follows 0 Lemma 2 For relatively prime positive integers m and n mn m n 0 Proof If m 1 or n 1 then the result is clear so we suppose m gt 1 and n gt 1 Let a1 lam denote the positive integers g m which are relativer prime to m and let 61 ban denote the positive integers g n which are relativer prime to n Suppose now that k 6 12 mn and 12 mn 1 De ne a and b by kEa modm 0 altm kEb modn and 0 bltn Since I a tm for some integer t and since km 1 we deduce that am 1 Similarly 671 1 Hence there are i E 12 m and j E 12 n such that k E ii mod m and k E bj mod n Since there are m n choices of pairs i j and k is uniquely determined by the above congruences ie because of the Chinese Remainder Theorem we get mn g m n Now x a pair ij with i 6 12 andj E 1 2 n and consider the integer k E 1 2 mn that exists by the Chinese Remainder Theorem which satis es 1 E ii mod m and k E bj mod n There exists an integer t such that k 2 ii tm so that since ohm 1 we obtain km 1 Also 12 n 1 Hence 1 mn 1 Therefore since each pair i j corresponds to a different k mn 2 m n Combining the inequalities we get mn m n 0 Theorem 15 Suppose n pilpgg where 81 er and r are positive integers and p1 pr are distinct primes Then W 1102 P quot 1gtquotH1 i1 pl 0 Proof The second equality is clear and the rst follows from Lemma 1 and Lemma 2 using Mn Pi1 Will 0 Examples Use the theorem to show that M100 2 40 and M140 2 48 o A sieve proof of Theorem 15 can be given that doesn t make use of the lemmas Observe that a positive integer m is not relatively prime to n if and only if m is divisible by some pj withj 6 12 For distinct j1 jk in 12 r the number ofpositive multiples of pjl pjk which are g n is n pj1 pjk The inclusion exclusion principle 15 implies that the number of positive integers g n which are not divisible by p1 pr1 or pr is z i1 pl jlltjzsrpjlpjz jlltjgltjgsrpj1pj2pjx mm pl The theorem follows 0 Comments An open problem due to Carmichael is to determine whether or not there is a positive integer n such that if m is a positive integer different from n then 7E n If such an n exists it is known that if must be gt 101000 Some result in this direction can be obtained as follows Observe that n E 0 mod 2 since otherwise n 2n Now n E 0 mod 4 since otherwise n n2 Now n E 0 mod since otherwise n 3n2 and n E 0 mod 9 since otherwise n 2n3 This approach can be extended apparently inde nitely as long as one is willing to consider branching off into different cases Homework 1 Calculate 180 and 10323 2 Prove that if n is a positive integer as in the comment above then n gt 1030 Hint Eventually consider two cases depending on whether 13n or 13 n During the year 1985 a convenience store which was open 7 days a week sold at least one book each day and a total of 600 books over the entire year Must there have been a period of consecutive days when exactly 129 books were sold Polynomial Basics 0 Irreducible polynomials A non zero polynomial E with i1 is irreducible over or in if with gx and in implies either gx 2 1 or 2 i1 A non zero polynomial E with i1 is reducible if f is not irreducible A non constant polynomial f E is irreducible over or in if with gx and in implies either gx or is a constant A non constant polynomial E is reducible over if is not irreducible over 0 Examples The polynomial x2 1 is irreducible over and over The polynomial 2x2 2 is reducible over and irreducible over 0 Comment Suppose f E and the greatest common divisor of the coef cients of f is 1 Then f is irreducible over the integers if and only if f is irreducible over the rationals 0 Unique factorization in It exists 0 Division algorithm for polynomials Given f and gx in with gx f 0 there are unique polynomials 130 and in such that qxgx and either E 0 or deg lt deg In the case where gx is monic the polynomials 130 and will be in 0 Examples If x3 2x 1 and 930 2 x2 2 then 130 2 x and 1 If x4 4 and 930 2 2x3 3x2 2 then 130 2 and 1x2 x o The Euclidean Algorithm Illustrate by computing gcdacg 1 x8 x4 1 Note that this example is not meant to be typical in general the coef cients might not be integral If we want gcd f x to be monic then division by a constant may be necessary after performing the Euclidean algorithm 0 Given and 930 in not both E 0 there exist polynomials and in such that WWW 9x39vx gcdfxgx The Euclidean algorithm can be used to compute such and o The Remainder Theorem The remainder when a polynomial f is divided by x a is f 1 Observe that the division algorithm for polynomials implies that there is a polynomial 130 6 and a rational number 7 such that x aqx r the remainder theorem follows by letting x a As a corollary we note that x 1 f if and only if at 2 0 o The Fundamental Theorem of Algebra A non zero polynomial f 6 Gas of degree n has exactly n complex roots when counted to their multiplicity In other words if f 220 ajxj 6 Gas is a non zero polynomial with roots counted to their multiplicity 11112 an then anx a1x a2 x an 0 Elementary Symmetric Functions Expanding the above factorization of f in terms of its roots we deduce that 2 an amen 1 023039 1quot0n where 01 0ti0t2 0tm 02 a10t20t10t3 0tn 10tmum 0n a10t2 0tn in general aj is the sum of the roots of f taken j at a time We deduce the formula aj 1janjan for each j 6 12 n Any rational symmetric function of the roots a1 a2 an can be written in terms of the elementary symmetric functions aj 0 Examples Discuss the values of aj when x2 3x 2 x 1x 2 Also given 11 a2a3a4 are the roots of x4 2x3 3x 5 compute the value of 1111 1112 1113 1114 0 Congruences Modulo Polynomials Is 3018 3x15 x6 x4 2x3 x2 2 divisible by x2 x 1 If not what s the remainder Discuss the answers Homework 1 Calculate gcdac5 330 1 3x3 6x2 2x 330 1 3x3 2x2 3x 1 2 Let a1 a2 and 13 be the roots of x3 x 1 0 Calculate SkZa fork1210 Determine whether 304 1 is a factor of x25 2x23 x17 x13 x7 x3 1 using arithmetic modulo x4 1 4 Consider all lines which meet the graph on y 2x4 7x3 3x 5 in four distinct points say xi yii 1 2 3 4 Show that 301 x2 x3 3C44 is independent of the line and nd its value Polynomials Modulo Integers Part I 0 Theorem 16 Letp be an odd prime The congruence x2 1 E 0 mod p has a solution if and only ifp E 1 mod 4 0 Proof First suppose p E 1 mod 4 Then p 412 1 for some positive integer k Thus p 12 is even By W ilson s Theorem we obtain 12p 121gtlt2gtltgtlt gtlt gtltgtltp 2gtltp 1 21x2xgtlt gtlt gtltgtlt 2gtlt 1 E 1P1V2 2 mod p Thus in this case x2 1 E 0 mod p has the solution x 12 Now suppose p E 3 mod 4 Then p 12 is odd Assume there is an integer x such that x2 1 E 0 mod p Then 302 E mod p implies since p 12 is odd that gap 1 2 x2p12 E 11 12 E 1 mod p This contradicts Fermat s Little Theorem Hence the theorem follows 0 Corollary There exist in nitely many primes E 1 mod 4 0 Before proving the corollary we establish Theorem 17 There exist in nitely many primes Proof 1 Euclid s Assume there are only nitely many primes say p1 pr Then the number p1 p 1 is not divisible by any of the primes p1 pr contradicting the Fundamental Theorem of Arithmetic Proof 2 The Fermat numbers F 227 1 are odd numbers gt 1 satisfying 111 2 H Fj j0

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.