New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Number Theory

by: Otilia Murray I

Number Theory MAT 115B

Otilia Murray I
GPA 3.88


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Mathematics (M)

This 33 page Class Notes was uploaded by Otilia Murray I on Tuesday September 8, 2015. The Class Notes belongs to MAT 115B at University of California - Davis taught by Staff in Fall. Since its upload, it has received 63 views. For similar materials see /class/187424/mat-115b-university-of-california-davis in Mathematics (M) at University of California - Davis.


Reviews for Number Theory


Report this Material


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: 09/08/15
Notes Math 115B March 16 2009 15 Continuation of Math 115A Some goals 1 Theorem that every prime7 p7 has a primitive root 2 quadratic residues Theorem Guass whether p is a quadratic mod q determined by whether q is a quadratic mod p x is a quadratic mod p means z E y2 mod p for some Quadratic reciprocity 3 Polynomial equations in integers and mod p Some review What primitive roots do for you Knowing that mod p arithmetic Zp has a primitive root7 7 an element of order p 7 1 makes 10m g Zp 7 17 a renaming or bijection that preserves important things Zp H Zp 7 1 rm 7 z a gt gt indra multiplication ab lt gt addition z y exponentiation ay lt gt multiplication zy addition lt gt eh nothing simple order of a7 0rdpa HEM additive order7 1st y such that zy E 0 mod p 7 1 or y L 90610671 7 1 primitive root b HEW prime residuey Therefore7 3 p 7 1 p primitive roots Recall n number of prime residues mod n An example 2 is a primitive root mod 11 1248571 727478 75 This corresponds to 07 17 2345767 787 9 What does this mean 71 lt gt ifp is odd In this case7 TL E 71 for any primitive root The equation 2 E 717 ie x4 E 1 and z i 1 or 717 ie x has order 4 x is like 239 2392 E 71 It is fair to say z E 239 it 7 E and 31 exists iff E 1 mod 4 primitive root theorem thus implies that if p E 3 mod 4 p X712 11fp E1 mod 4371 such that p E 131017112 1 17 We looked at consequences of the primitive root theorem Theorem 1 lfp 21 mod 47 then Zp has 239 or solution to 2 E 1 mod p 2 lfp E 1 mod 47 then Zp does not have 239 1 eventually gets you p a2 b2 if p E 1 mod 4 and prime Note 71 217 a2 b2 part 1 of the theorem also says that 10an 1 for some n 2 gt theorem below Theorem 300 many primes that are 1 mod 4 Theorem 00 many primes Proof Suppose that there only exists k a nite number7 primes with pk being the largest prime Let n 101102 pk Then7 3 S 71 1 has some prime factors since 71 1 gt pk so CONTRADlCTlONHH Theorem 00 many primes that are equivalent to 3 mod 4 M Suppose that there only exists k a nite number7 primes that are equivalent to 3 mod 4 with pk being the largest Let n p1p2 pk Let7s look at 471 1 Of course7 its equivalent to 3 mod 47 so not all its prime factors are 1 mod 4 and none are p1 pk Pretty much the same as the one above Not a Proof For primes that are equivalent to 1 mod 4 Let n p1p2 pk Looking at 471 1 or n 1 does not imply that that any of their factors are 1 mod 47 although happily their factors aren7t p1 pk Real Proof Let n 101102 pk Look at 4712 1 None of its prime factors7 q7 are among p1 pk want at least one q to be 1 mod 4 Even better7 they all are q 74 2 q i 3 mod 4 because as we said by part 2 of the theorem7 if it were7 then q X2n2 1 gt 00 many primes equivalent to 1 mod 4 Theorem prime number theorem lf 7Tn is the number of primes les than 717 then limyH00 Let ab be the number of primes less than n that are equivalent to a mod b For each b7 there are phz39b interesting choices of a7 namely a 1 b W H a by then hmnm m l have heard that 7Tl39j1n and 7T34n are 77unbalanced in the sense 7T34n gt 7T14n usually or always Theorem 3 a primitive root mod p 19 Theorem Langrange lfp is prime7 042 is a integer polynomial of degree 717 then 042 E mod p has 3 n incongruent solutions 042 0 Compare with7 ln Q or R aa 0 has 3 71 solutions In C 042 0 has exactly 71 solutions counting repeats Polynomials mod p in general If we say that 042 E 62 mod 717 it could mean that the coef cients are equivalent or the values are congruent They7re not congruent situations The former is the usual meaning and is stronger The former implies the latter Example 71 2 Let7s claim that 22 2 E 0 mod 2 There are only 2 cases7 01 02 0 E 0 and 12 12 07 so its true They7re not equivalent as polynomials Proof of Lagrange s theorem Uses induction on degree of 1 and Primality Lemma Primality Lemma lf plab7 then pla or plb Base case Let deg1 0 where 1 i 0 We want to know that 1 has at most 0 roots mod p This is true because 12 1 mod 0 where b i 0 has no solution since no matter what 2 is7 12 i 0 since it is E b lnductive case We have 127 say 2 r is 1 mod p roots Otherwise7 if there is no 7 were done Then7 12 17 say I mean in Z J E 0 mod p or plb We can change 12 to 12 12 7b7 doesn7t change the situation 7 is an ordinary root of 12 12 2 7 r02 12 E 2 7 r02 mod p I claim that if s 7 r0s E 0 mod p where s 7 r then 05 E 0 mod p Yes7 this is true because p 15 7 r so 10105 or i exists mod p 12 E 2 7 7quot027 so deg1 717 deg0 n 17 02 has 3 n 7 1 roots Claim says 12 has the roots that 02 does p is at most one more7 so 12 has 3 n roots Theorem A polynomial with coef cients in any eld factors uniquely into irreducible polynomials Proof is similar to the unique factorication of integers last quarter Its a bit more abstract7 but the idea is still the same Recall7 we will care about 2k E 1 mod p In general7 12 E 0 mod p is hard to solve when p is big The S deg1 solutions is only easy part What about 12 E 0 mod n where n is not prime Example 23 2 5 0 mod 21 3 From the Chinese remainder theorem aw E 0 mod n gt aw E 0 mod prime power factors of 71 That still leaves aw E 0 mod p M mod 49 lt gt mod 7 BUT mod 49 gt mod 7 So from our example x3 z 5 E 0 mod 49 gt x3 z 5 E 0 mod 7 So our plan solve mod pk l First say z E 7 mod p Then lift z E r tpk l mod p It exists mod p This is called Hensel lifting TheoremHensel the equation for t is linear and uses aw 112 Hensel lifting were looking at aw E 0 mod pk n to pk by the Chinese Remainder Theorem First look at aw E 0 mod p which could be hard when p is small its not hard Lagrange says there is less than degreea solutions Then work by induction on k The set from k 7 1 to k is called Hensel listing Suppose ar E 0 mod pkquotl If we know 7 mod pk l pick some choice mod p then all choices mod pk are r tp exists for matters of mod p 17m thinking of some a b gtk 100 mod 1000 Then b exists for matters mod 10 In general ifl have b gtk k mod n where k n are xed then b exists for matters mod m b matters for mod 10 because 1000100 10 k 1 where t Example 2 E 71 mod 5 eg x 2 works Now x2 E 71 mod 25 ls z E 2 mod 5 Maybe If so z E 2 5t mod 25 It exists mod 5 Despite the fact that we started with non linear equation t is still linear even when lifting 2 E 2 5t2 E 4 20t 25t2 27 712 24 mod 25 Then because 2 works mod 5 5 constant parts of the equation Therefore 20t E 75 mod 25 4t E 71 mod 5 1 t if E 1 mod 5 4 So z E 7 mod 25 works Ok so what about mod 125 mod 54 part of Hensel7s Lemma ar tpk l 7 ar E tpk la U mod pk ln calculus derivatives follows from sum and product rules and from c 0 and x 1 and induc tion Claim is bt r E artpk 1 iar mod pk is psuedo calculus in the sense that the derivatives holds with a factor of tpk l lfa c bx cic0 lf aw s bx z tpk l 7 z tpk l Product rule We have a1xagzb1txb2tz Then say 13x a1agx and b3tz 7 a1z tpk 1a2ac tpk l E 0196 tpkilaiaz9 tpkila E 1960295 t10k 1al0296 kWh96 So Hensel7s lemma 1st form is true The second form is how you use this to solve things Have ar E 0 mod pk l where r is some lift not necessarily 0 mod pk ar tpk l E ar tpk 1a r E7 0 mod pk so rtr E7 791 mod p Hensel7s lemma says the solution mod pk amounts to a rt E 7 mod p There are three cases 1 rtr i 0 mod p there is a unique solution for It You can keep lifting forever from p to p2 to 2 rtr E 0 and ar i 0 mod pk there is no solution 9 both E 0 t can be anything Example 2 E 71 mod 5 12 2 1 and rtz 2x z E 2 mod 5 12 4 i 0 mod 5 so 3 a unique lift mod 25125 Hensel also de ned p adic numbers which are numbers in base p with in nitely many digits to the left 116 Ordinary numbers in R have nitely many digits to left in nitely many digits to the right carry rules for 7 gtlt optional minus sign and different bases b represent the same R We know that 7139 314159 De nition lfp is prime p adict number has in nitely many base p digits to the left and nitely many to the right and carries to the left set of all of those us written Q17 p adic numbers Those that have no digits to the right are p adic integers Z1 M Zp 31 Zp WA is uncountable lZpl 1 Example Z5 00005 0 00000345 345 19 Lets say I have 44445 05 05 that means that 444444 0 Can subtract anything from 0005 in Zp Therefore minus signs are optional Another de nitionexplanation of z E Z1 is that its any consistant sequence of residues mod pk as k a 00 Example I want z E 2 mod 5 225 mod 25 122225 mod 125 E 62 z E Z is sometimes Z Q Zp This z E 7 because z E 7 mod 5k Vk Jesus said 2 E 71 mod 5k has two solutions for aSll k Therefore it has two 5 adic solutions so z 125 solutions to 2 71 E Z5 Theorem 1 Z s are all inequivalent rings all inequivalent to R or C Example Z5 i R because i E Z Theorem 2 Q is closed under division Actually everything Z17 can divide by any x such that p Can make Z for composite n gt 1 too but they dont add much to Zp7s 121 x E Z is like an integer except when it has in nitely digits to the left in base p Example 4445 0015 0005 As we can see 4445 71 0015 1 and 0005 0 Example 125 125 445 there exists a way to ll remaining digits so that x2 71 E Z5 A p adic integer z E Z is the same as any consistent set of residues mod p mod p2 z E 2 mod5 z E 7 mod25 Hensel lifting p adically base p Lift 2 E 71 mod 5 z E 2 mod5 z E 7 mod25 To get to mod 125 as in the book z E 7 t25 mod 125 Recall ii has used for mod k value of n t125 gtlt t125 21245 t125 t or t 12f Confusing Yea We end up ignoring the t7s at the end anyway since we only have three digits So we have 4t 3r 1445 If we wanted x2 E 716 Z5 got 4t1E 4 mod 5 t E 2 Remember 445 E 71 which is why we wanted the digit 4t 1 to be 4 Other fun facts 1 Zn 71 not prime Zpk g Z17 ie 2 adicts and 8 addics are equivalent 6 2 Every Zn is a commutative ring 3 Q17 is a eld 4 If n is not pk7 say 71 pflpgz 1022 then by the Chinese Remainder Theorem7 Zn g Z171 gtlt gtlt Zpa Example Z10 Z5 gtlt Z2 by the Chinese Remainder Theorem a 10 adic integer lt gt a pair consisting of a 5 addic integer and 2 addict integer z mod 1000 lt gt x mod 125z mod 8 Mobius inversion Leading to existence of primitive roots Recall that Mn 71number 0f Prune dmsors 0 if n is square free 0 otherw1se Let fn be some function Let Ed n d where fd is a summatory function If we know Fn7 what7s fn for all n ie f9 F9 7 F3 ie f12 F12 7F6 7F4F2 This is inclusion exclusion with two subsets divisible by 6 and 4 General inclusion exclusion formula for sets Number ofelements in U not in As where Ai is each subset of U Z Vii 7 lAl figHZ lAl H A H Akli Mobius inversion is an adaptation of that fn Fn7F Z F7Fm pln zuzln but met A 71 number of prime factors of d 1 117 dln and is square free Back to the example7 f12 F12 7F60F3 7F4F20F1 123 More Mobius inversions fn is some function and is the fn7s summatory function 1 Edi fd You can also nd fn from Fd too fn Ed n pdF Ed n pFd Most important point You have a bijection between f and F Example Last quarter7 we learn the following o Tn is the number of divisors of n o on is the sum of divisors of n o n is the number of prime residues mod n Tn is the summatory function of fn 1 Ed 1 so 1 Ed urd on Ed d so on is the summatory function of fn n making n Ed uod What about n7 Theorem 3 The summatory function of n is n so n Zdlnmd example and idea Let n 10 The plan is to assemble Z10 From Zdm for dla Proof If a E Zngcdan d for dln Segregate Us by this value For each of them there are g choices for 1 because a db b E Zgy D so n Ed 153 Edi Md Theorem 4 Primitive root theorem pr is prime then Zp has a primitive root r an element of order p7 Then the elements of Zp are powers of r Then there are 151 7 1 primtiue roots rm where z E Zp 7 Actually well go straight to this What we need for this proof 1 Lagrange7s theorem We have 3 degree of ap solutions to ap E 0 mod p 2 Number of solutions to 4 E 1 mod p is p 7 1 3 The de ntion of fpn and Fpn 4 The lemma that will be introduced later De nition 5 o fpn is the number of residues of order n mod p o Fpn is the number of solutions to x E 1 mod p where ordpxln If you let d ordpx de nitions give us Fpn Ed n fpd Our goal is to show ZpV are a big circle ie Fpn nwhen nlp 71 gt fpn n when nlp 71 Today7s lemma Mobius inversion Lemma 6 Ifnlp 7 1 then x E 1 mod p has epaetly n solutions Proof 74 71 z 7 1 gtlt ap On the left side we have p 7 1 solutions x 7 1 has at least n solutions degree of ap is p 71 7 n We know that dab 7 1 pa 7 1x b 1174 pab ga x 1 8 Recall a is a quadratic residue mod p means that its a square mod p 1 ifa is a quad residue arid a i 0 mod p De nition 7 Legendre symbal 71 ifa f 0 mod p arid riot quad residue 0 a E 0 mod p 126 Quadratic residues lfp is prime and a large one most a E 0 mod p are hard to solve or even to count solutions for computer with known algorithms x E 1 mod p is a special and easy to count solutions The number is the gcdnp 7 1 It is easy to nd them too if you obtain a primitive root r x E 0 mod p is hard again even for most small 71 ie n 3 Even counting solutions even I think if you have a primitive root and can factor p 7 1 How you use primitive roots Zp Zp71 7 m a gt gt indwa Why not take discrete logs indwx E n gtlt indwd E indwc mod p 7 1 But this is hard to nd 77Discrete logarithm problem77 BUT n 2 where m E N is the big exception You can count solution to 2 E 0 mod p and even nd them Shanks Tonelli Traditional and convenient form for two types of c 2 E c has or doesnt have solutions is Legendre symbol 0 i p 71 if c K p and 0 solutions In the former case 0 is quadratic residue In the latter case 0 is non quadratic residue lf plc we have two conventions i is unde ned or its 0 1 if c 1 p and two solutions First properties 1 depends only on a mod p The real point fa is either a function on Zp or an Z Both interpretations are important ab 7 a b i 7 i i i i 2 g 7 EE So it s completely multiplicative in a For the second property Not so hard if are 11 or 1 71 or 1 1 But 1 17 If a E 2 and b E yz then ab E lnteresting case a f 2 and b i y2 for any or y i ab E 22 9 Proof For the second property Say we have primitive roots and p is odd Then a E x2 mod p Take logs and you get j E 2k mod p 71 where a E rj and z E rk 1 when 2 39 If a E N then 9 E D p b 7 b swerexp A Then Just becomes addition of exponents mod 2 So 1 L times This is also true because z gt gt x2 is 2 to 1 D 71 when 2 Xj Back to the rst property depends on a mod p 10000 For example 31 You can divide and take the remainder Can you relate to g Then it would be step 1 towards an Euclidean type algorithm to compute 17 Theorem 8 From Gauss Up and q are odd primes then 3X 71 e 5 if at least 1 ofp andq 239s1 mod 4 egtsegtop2q23rmd4 oilqil 2 2 128 Computational Context Corrected 1 Discrete logartihms are hard If a E rm mod p solving for x 2 Solving aw E 0 mod p is not hard where degree of a is low ie For each xed k if degreea S k gets harder only slowly as p increases It does polynomial time in number of digits of p but it gets harder much faster as degree of polynomial increase z 0 mod p its fast to count or nd solutions z 0 mod p too and so is any x E c M 7 c is moreever a special polynomial Finding solutions is 77Shanks Tonelli Counting solutions to these equations is due to Euler Theorem 9 Euler E apTil mod p Proof Take logarithms a E rm mod p where r is a primitive root to m p 71 if z is odd 12 mod 2d Trivial case since we are looking at large prime numbers which are odd z exists mod p71 71 x mod2 f7 gtltn So rm 71 iff z is odd We know that 1 if z is even Example r 2 and mod11 2w5 is 180 degee times z way around the circle so you get to top 1 if z is even and bottom 1 if z is odd 10 D By some type of argument if klp 7 1 then a has a kth root modp iff aLkl E 1 mod p What were curious about with quadratic residues What digits can n2 end in 0 145 69 and not the others in base 10 1e For what p is 1 modl357111317192 2 4 1 1 1 1 1 1 6 22 mod 17 Gauss amazmg 1st steptoreplace exponents p in Euler by products products by sums Lemma 10 Say p is odd and a 1 p Then 9 1 if an even number of least prime residues of I7 1 2a Ea are between and g 71nnmber 0f aj s that are 772nd half mod p when 739 is 7715i half mod p 17 Example 1 3p 13 j123456789101112 3 aj 3 6 912 2 5 81114 7103039quot all the residues of aj Count all the number of residues of these that are gt ldeaoftheproof Compare123Esandagtk2agtk3agtkgtka2t 712 1 Take the rst L j7s Find 130 Quadratic reciprocity thm 1st criterion and de nition if there exists x a solution to 2 E a5 77a on p77 71 if not 0 if p 7 a 1 a 2 modp 715 where s is the number of left half residues 1 S j S L S 17 mod p S p 7 1 2nd criterion is Euler7s lemma E 3rd criterion is Gauss7 lemma such that 17 is the right half 21 7 Proof Compare two products mod p z1gtlt2gtltgtltp21 modp yagtlt2a gtlt3a gtltgtltL1a modp is 1st of all de ned on mod p p 71 L a gzaxaxgtlta2a 2 25 5 is the number of left half j7s with 17 is the half Let G 1 2a 1271a all of which has a different equivalence mod p 6 No two elements of G are negatives either 17 E iak then j E 7k can7t happen if jh are left half this happens 5 times so E 715 also 2 g 7 s n77lt u D Example 1 3 p 11 z E 1 gtlt 3 gtlt 3 gtlt 4 gtlt 5 y23gtlt6gtlt9gtlt1gtlt4EBgtlt75gtlt72gtlt1gtlt4Ezgtlt719withseinthiscase Theorem 11 Using Gauss s Lemma 1 102107quot mod8 71 otherwise 47 1 ipr1 mod4 T 71 iprB mod 4 Proof 715 where sis s in this case 71p21 i 49 ie number of1 j L21 such that 271 and 2739 ltp Let s be the number of g lt 2739 lt p where p is odd Then the number of 2739 lt p is L which is even ifp E 1 mod y and odd ifp E 3 mod 4 Then the number of 2739 lt L is 1 which is even if p E odd mod 8 and odd otherwise SEOipr1or7mod8and1ifp230r5 mod8 D Lemma 12 39 Gauss Lemma i 715 where s E 2 mod 2 22 Gauss Lemma 715 where s number of left half residues j such that 17 is right half a 2 a mod2 71 192 Geometric Interpretation Let t be the number of lattice points inside of a triangle Lattice points are points with integer coordinates The triangle has vertices 00 41 g 0 The slope of the line is i The points on the hypotenuse is The number of dots inside the column of 17 is where p X2 17 Lemma 13 Also ifa is odd 5 E 271 mod 2 Want to show gg 711 1 I Let t1 V731 g t2 271 l1 Then 5 71 and 1 71 by Eisenstein7s Lemma as HW 7 452 q 12 Using the geometric Interpretation again Think of a rectangle with x length7 g and y length7 Let there be a diagonal of the rectangle with slope Count the lattice points Bottom triangle has t1 lattice points and upper triangle has t2 lattice points The total number of lattice points in the rectangle is L21 The reason is because there is lg on the columns of bottom triangle with endpoint on hypotenuse and 1 ng dots in row The only thing missing is a proof of Eisenstein7s lemma itself Lemma 14 Also ifa is odd 5 E 271 mod 2 Conjecture number of j7s such that is odd Working mod 2 1 Ep E 1 Also7 77 E 7 Following book7 write aj pl remainder The remainder is either 1 S u L What the remainders do 7 aj07 so as in Gauss7 lemma7 get each u once Get p 5 times I So7 let7s sum aj pl remainder over 1 S j S L E L1 a a 12 07 ijil 10 X 5 Zuiiu mOd 2 41 41 You are then left with 2721 s E 0 mod 27 so 5 E 2721 Eisenstein7s sum mod 2 21 pl S So7 where now Want Euclidean style algorithm to compute 7 but what if a isn7t prime Then7 so if you can factor top7 you7re ok De nition 15 the Jacobi symbol is by de nition H iw ifn pll1 1953 Not really comming from mod n arithmetic Doesn7t solve a E 2 mod n or count solutions mil 71 It is de ned7 so that 71TT when ab both are odd7 even if composite 24 The Jacobi symbol If n ms pin then g 581 as Right hand side is the Legendre s mbol and left side is the Jacobi symbol Legendre is only de ned for odd primes lf gcdan gt 17 let it be 0 There is no particular interpretation at rst This is set up so that quadratic reciprocity is still true and the laws for and Easier Harder Easy 1 as as Easy 2 be so is completely multiplicative in a and separately in bA lot like dot products Hard 71ni1 for odd 71 Hard 71 1 for odd 71 mil 71 Hard Jacobi7s reciprocity 71TT Why is Easy 2 true lt7s engineered by de nition Prime factors of gc prime factors of bprime factors of c7 so expanding gives same thing as expected and Why is Easy 1 true ab 1 b ab 1 b g EXE is true for legendre symbol7 so and these are factors of 7 E and E So7 let7s check in Z 8 1 0 1 3 1 1 71FTE1 and 3X 71L1 are other versions of the same trick pq 5 3 1 7 6 1 only matter mod 4 Proof Hard 3 by Easy 1 and Easy 2 is 77bimultiplicative just like an inner products is bilinear ltabgt is also bimultiplicative just like an i710 is determined by its values on a basis which you make into a matrix is determined by its values on primes pilqil lt gt 1 2 2 So7 if is 1 bimultiplicative too and 2 has the same matrix Let g 71 Same matrix when a p7 b q Yes ls it bimultiplicative ls it true that and some on the other side Yes7 just check all eight cases mod 4 D This is really a proof by induction that 71a1b1 using easy 1 and easy 2 g h ltbgtlt gtlt c n l m n27 71T1 is the same plan Both sides are multiplicative in n and when n is prime vs ls a a square mod n Say 71 p2 where 2 17 so a is not involved at all and we dont know whether a is a quadratic residue or not Lets say that n is square free n 101102 pk with all primes being different a E x2 mod n iff 1 for each prime factor 1 iff 71 for an even number of prime factors 26 Why 71T 2 when 11 are odd and positive a 14 1 Both sides are bimultiplicative The left side comes from de ntion The right side are cases mod 4 2 Equal when ab are prime quadratic reciprocity Likewise 71ni1 and 71 1 n 1 Both sides are completely multiplicative 2 when n is prime Gauss7 Lemma and in a only matters mod n i algorithm to compute Jacobi symbol Legendre symbol According to the book is de ned when n gt 0 a lt 0 or a gt 0 I disagree Let 1 Then to make all of the laws still work Example The second step is bcause 101 is 1 mod 4 and so is719 NOW7 3 g 3 1 1 2 1 what if a or b is even 12061 gt h MSG gl 4 c g when both odd can reduce a mod b in and and T20 is known and E i a version of Euler7s algorithm Miller Rabin is Miller7s test choosing at random lt exposes that n is composite of at least 3 quar ters of the time Then n is probably prime or is is de nitely composite Special cases Fermat numbersprimes ls 2 1 prime If it is either n 0 or n 2k Mersenne primes Primes that are 2 7 1 Theorem 16 If fk 22k 1 as fermat and h gt 0 Then a 2 is not interesting Then a 3 CCEPOSCS composite fk for sure Then in fact 3 xiii Why is 3 2 E 71 when fk is prime if direction Proof E 71 mod fk i fk is prime 3 fk fk 3 22k1 3 42k71 3 by euler7s lemma Quadratic reciprocity 29 Jacobi symbol and primality tests for 71 Lets say 71 odd If n is primep there are two ways to compile E a E 1 Euler7s lemma 5 E a 2 mod p 2 Extension of Euclidean algorithm using quadratic residues of p But if n is composite only have part 2 to compute Thus a primality test Solovay Skossen If n is prime then E anTil mod 71 These could happen even if n is not prime for some a If it happens and n is composite n is an 77 Euler pseudoprime M lf aLEl E mod n then an 1 E E1 mod n Euler psuedoprime vanilla a psuedoprime Miller7s Test is stronger than Euler7s test Theorem 17 fa is a Miller a pseudoprime theri a is a Euler a pseudoprime Let 27171 7 1 such that 7 1 is odd R71 R71 Then 1fn1s prime a 27 a27 1a 11s either all 1s or 711 The strategy for either test is chosen at random to make 71 either composite for sure or probably prime Theorem 18 Miller Rabin At least 2 of reults reveal n to be completely by Miller s test Theorem 19 Soloyay Strasseri At least i of reults reveal n to be completely by Euler s test Theorem 20 Baby Soloyay Strasseri Ifn is composite 3a 1 n such that an 1 i mod 71 Proof say it wasnt so for some ii an 1 E 1 mod 71 Va 1 n so 71 is Carmichael n is square free and p 7 1171 7 1 when pln Say pln we supposed anTil E 11 mod p Let k re p 71 apT E 11 mod 1 apTk E aTl and h is odd because ap lz So where we are anTil E ap 12 mod p when pln By hypothesis anTil and by fact Thejrefore i i If pqlnthen This can7t happen because a is modp of aD mo q Example Let n 561 3 gtlt 11 gtlt17 If this passed Euler7s test then Va 1 n then 1 7171 p71k Vpln and 2lt gt g E Z7 Rational and irrational numbers well be doing this in Q Q R and in Q17 Theorem 21 a E R is rational i it s a repeating decimal Proof Depends on how long division works The algorithm determines by the remainder If the re mainder ever repeats7 when you7re pulling down 0s7 then the whole algorithm repeats after that Repeats must happen because there is only nite choices of remainders The converse lf digits of a repeats7 then a 2 cases 1 Terminating decimals Yes Ex 7215 7215 1000 2 Repeating from start 99999999 17 237 001001 and 237237 C 211 Repeating decimals and fractions fractions gt repeating decimal Now7 repeating decimal gt fraction 1 A terminating decimal is a fraction 10 where n is the number of digits OR in base d7 1 Note decimal points can be used to express a E R in any base 2 Pure reptition7 0 lt a lt l and repeats from beginning a digits of some k eg7 a 237 so 000 l 10371 Finally7 every 04 terminating repeats from beginning Another argument that fraction implies repeating decimal is based on converse direction f Wig W071 then yes Claim is7 this is possible if b L 10 Another claim 371 such that M10 7 17 10 E 1 mod b Yes7 n ab7 for instance7 Euler7s theorem ln base d b 1 d then d ltbgt 21 mod b g What if gcdb7 10 gt 1 or gcdbd gt 1 Can we x that by multiplying and dividing by the base Example 1 1 3 A general7 if k is big enough 10 3 All of this still works in p adic number Q17 or even in n adic number Q Q17 is Zp except with dividing by p allowed and realized by nitely many digits to the right ofthe decimal Example 4443 71 333345 Theorem 22 In Q or even Q fraction gt repeating digits Q is a eld ka Q17 gtlt where pqln has 77zero division ab 0 ab 31 0 In R in base p 142857 and 7 142857 218 Midterm question 1 77700010 1000 gtk 77710 p addicn addic convergence of sequences or series limH00 xk z and mm E Z or Z means limH00 dzkx 0 where dab 2 l where pl or nlla 7 b and pH1 or 71 1 la 7 b Example a 2375008 I 1375008 dRab 106 a lot d10ab 2 6 small It converges 10 addicly Geometryic series formula k 7 b ZZZon Q Why don7t we just test it out in 10 addictly 220 7 gtk 10k 7g which is what it is 10 adically right n addic criterion is dna0 a Va Theorem 23 39 e is irrational where e 2 220 Proof Use 77 factorial base xddxzxxzxxddzwxzdzzxd Everything to the left of the decimal point is base 10 First place right of decimal point is base 2 next is base 3 next is base 4 Ontheother hande211111 22714 On the other hand if is rational then which terminates eg 0104fac Assume that an estimate Let oz 6 R and consider approximating oz by except for oz oz but oz 31 Theorem 24 Ifoz E Q then loz 7 gt f depends on oz but not b loz 7 small with b not too big is called diophantine approceirnation In our case loz 7 where means 2 efn Proof oz g y x a lxb 7 ayl y ab 1 gt i yb l 7 p D Back to the proof Proof How well does e work in la 7 To well Sn 220 is a close rational n e7snlmlt l7 9i7soe lt D Theorem 25 fa is algebraic of degree n then la 7 9 220 Irrational and transcendental numbers oz 6 R is algebraic means fa 0 for some polynomial with integer coef cients This generalizes root constructions Theorem 26 If fa 0 where coe cients of f are algebraic then ga 0 where coe cients are integers interesting ideas 7139 is not algebraic Even though its from a circle7 you use calculus to get the perimeter of the circle and areas of the circle oz is transcendental if it is not algebraic Theorem 27 Transcendental edists Theorem 28 e and 7139 are transcendental Proving e and 7139 are irrational is very dif cult7 so we wont Theorem 29 27r is irrational and transcendental No one can prove this Lets say that oz Then7 fa 0 where fa a 7 bx so rational numbers are algebraic Proof 1 of transcendental existence Set A of algebraic numbers is countable7 but R is uncountable Computer Science approach to countability If S is a set of elements described by nite words by a nite alphabet7 then its countable Order 5 as words of length 1 in alphabetical order7 then words of length 2 in alphbetical order7 If x E S has many names7 just use the rst one 19 Example Q is countable Alphabet 01 9 Just use lowest term My dictionary 0 1 2 3 9 10 11 99 1 9 100 199 12 19 200 oz 6 R algebraic described by a word with alphabet 0 1 9 X For the polynomials 2 is described by 7 2 2 where g is the separator The last 2 is the kth root from smallest to largest 7 2 2 means 2nd root of 2 7 2 0 Proof2 lfozEQloz7lgt 7 gigilwbiwl detail12 bli by 2 when 04 31 81H ll Theorem 30 fa is algebraic number of degree n la 7 2 i so if we choose 04 very close to it s transcendental Theorem 31 x 1100010000 010 01 Say fourth Z is on the 24th digit and fth one is at 120th Well z 20110 m Let x where b 10 Then la 7 g 104W 3 2 gtlt 10iltr1gt la l 2 1 Proof Idea is if f is a polynominal of degree n with coeffcients E Z can bound fltzz37z1lz7 71lm 2 223 Prove that e is irrational e2lli 2 6 24 converges quickly The tail 1 1 denominator of partial sum In fact The tail lt Til gtlt 1 denominator of partial sum 2nd proof of e is irrational lfaEQbutoz7 la 7 gt 00 contradicts tail lt Ll n1b39 Theorem 32 7139 is irrational Lemma 33 Iff is a polynomial of degree n with integer eoe eients and f then 2 1 Proof Proof of the Lemma Combine denomiatorsl Get some integer over b 20 04 04 043 04 2 3 mm 7 2n 7 W 2 bi Now7 let In f0 x xx sinx We know that In gt 07 but less than am n Inltasn7oogoest00 i n 0 1 2 3 4 ln fact7 it goes very fast In 2 4 24 i 2W2 H Lemma 34 In is an integer polynomial in 7139 In fact in 7T2 7T2 is irrational Continued fraction 1 oz a0 1 a1 71 a2aa is called the continued fraction expansion of at Various theorems All continued fractions converges to different 04 E R and every 04 E R is reached and cfe of 04 is nite iff oz 6 Q 225 Continued Fraction A nice corollary to continued fraction Theorem 35 by Dirchlet Ifa Z Q anda E R then la 7 lt 1372 for in nitely many Theorem 36 Ifa E Q then 30 depends on 04 only such that la 7 either is U or greater than Examples la 7 00012 lt i le7 08 lt i not good enough lfigl014lt Dirchlet7s theorem is proven by continuous fractions Say that is a record setting approximation to 04 if la 7 lt la 7 glVd lt b and 31 3 Example xi m g 6 4 3 1 I E i and I are still good approximation Theorem 37 All record setting comes from continuous fraction eccpansion of 04 A continuation fraction is denoted by aog a17 7an nite or aog a17 in nite Both means that laol 10 21 and l l 1 aoga1a0 11 12 More rigorously if you chop a continuous fraction to ck 10 a1 ak Then 10 a1 is by de nition limH00 ck Theorem 38 Z limH00 ck always CCElStS 2 limits di er for two di erent continuous fractions 3 Every 04 E R is reached Let7s suppose all that Take 04 E R Then l l 1 oz a a a 7 0 1 0 11 Sayoz 26 10 2 m a gt 0 for all i In a0an an gt 2 In fact this shows part 2 by induction By this relation if 04 aog a1a2 l then 1 1 O a1 a2 70 Not a convergent We chopped off head not tail so they7re all unique J liabli Theorem 39 fa tne remainders in continued fraction eccpansion ofa eventually reach k WM or T i continued fraction eccpansion repeats Theorem 40 Converse is true If continuous fraction eccpansion ofa repeats then a is a root of a2bxc0 abc Z nd Proof Suppose oz is rational then by the theorem continued fraction expansion of oz terminates In fact its just the euclidean algorithm to compute gcda b Maxab in remainders keep decreasing gimme Q l where q Therefore continued fraction expansion of terminates 1 22 227 Continued fractions Example 1 1 111 Estimates 1 1 1 1 1 1 3 2 2 1 5 1 7 7 g 3 1 8 1 g 7 g 5 This follows the bonnaci sequence 1 b 1 3 l a E a Let7s derive the limit independently lf1111zthenx1andpgt1thenz2z1 Therefore 127 Two important lessons from the example 1 Always bbonacci like recurrence for numerical denomination of Ck 2 It continued fraction of c is periodic then it is a quadratic equation for x De nition 41 a0a1 is a simple continued fractions means ak E Z You can write it down for any values Example Not simple 1 e 1 egm 7T 1 E Lemma 42 Fibbonaccish theorem Let 51 1 so a0 5k aksk1 ska t1 0 t0 1 tk aktk1 tk2 where h 2 1 Then Ck a0 a1 ak Si tk 39 Ck may not be a simple continued fraction and the fraction is sustanominalfraction Theorem 43 If a0 a1 ak is simple 7 is lowest term and 5k and tk are integers Proof By induction on k Suppose we know this for some k 1 Ok1 107017 7ak1l 107017 7ak717ak il 23 ak1 Let C be the kth term of in the continued fraction akskil Skiz 0 k alt tH ti 6 ak15k71 Skiz 7 6 wil kil M72 Ska i akskil Skiz m i t aktkil M72 1 ak15k Skil ak1tk tkil 5k1 tk1 We just need the base case and we proved this D Theorem 44 Sktkil Skiltk illkil if a0a1 ak is simple From this theorem we know that gedsktk 1 where gedsktk 1 gcdsk sk1i1 gedtktk1 1 The proof of this theorem is done by induction too One of the goals were after all simple continued fractions converge We need the following lemma to prove it Lemma45 COlt02ltC4ltltltC5ltCglt01 always happens in simple continuous fractions The proof of this lemma is done with the previous theorem 32 Continued fraction 04 a0a1a2 ck Somehow found a recurrence for 5k tk sktk1 7 sk1tk 71quot1 i gedsktk 1 Matrixslope point of View A linear map or matrix on R2 takes lines to lines Lets take the lines through 0 and so it takes slopes to slopes Say M Z l a 3 l 2f cdm M takes slope z to WM 3 A bit more standard d c J H ax b M b a cxd This kind of function of X is called a Mobius transformation A fractional functions is linear transformation or rnapping When you compose two Mobius function f1 f2 you should multiply their rnatrices you will get another Mobius function f3 m You can throw in the slope 00 m Just so we dont confuse ourselves we7ll just have the matrices E map to the frac tional linear equation lf then foo g and In other words it is still included in the map So how is this related to continued fractions Say 04 10 a1a2 Ck 00117027 7akl Let Dk 01027037 7akl which is basically Ck with 10 chopped off and a rnoved to ll1 or in other words 1 aoDk1 O 7 k a0Dk 1Dk0 In other words its a fractional linear transformation with matrix Ck is then the slope of These rnatrices rnultiply to The determinant are all 1 so the determinant of Ck is 71k l or 71k 1 Therefore sktk1 7 sk1tk 71kquotl The books recurrence is 5k 5k71 5k71 5k72 1k 1 M tk71 tk71 M72 1 0 This implicitly uses that matrix multiplication is associative Convergence of Convergents Oz 10 11 except does the right side always converge CO 10 1 Ci 10 i 01 l 02 ao71 12 00 lt all subsequent numbers in the sequence 01 gt every subsequent numbers because 11 lt 11 00 lt all subsequent numbers in the sequence Tosummarize COltCZlt lt ltO5ltOg lt01 lim 0 exists and lim02k1 exists Are they equal They are equal iff Wk 7 OkHl 7 0 Let t 7 7t 7 l OkiOkil l5kk 1 Wk il o tktk71 tktk71 04 is between two consecutive partial continued fractions so 1 Oz 7 Ok lt 7 lt i tktk1 It So we just got Dirchlet7s thoerem 34 04 m is 77best77 means that 04 7 gt la 7 5 i d gt b Theorem 46 If Ck 7 is a convergent Ufa then it is the best In fact if there erists is better 5 Z tk1 An even better theorem Theorem 47 ltkoz 7 skl gt lboz 7 al i b 2 t1 L Ifb lt 5k and ltkoz 7 skl gt lboz 7 al then this is weaker than being closer 26 Periodic continued fractions Suppose oz 00117027 b1 bl Then7 what can 04 be The right side does converge can use this solve for a Lemma 48 f aog a17 x is a fractional linear transformation Proof 1 an 1 ak z i bx 0 ls 1 over a fractional linear transformation a fractional linear transformation Yes ls a fractional linear transformation a fractional linear transformation Yes ajxk 7 alxmjxk lxm i lxm i aljamk lxm Case 1 oz bogb1bl so 1 aab b a 0b1 cad by the lemma 04 is a root of z 313 which is approximate to a quadratic equation General case If bog b1 bl Let oz a07a1ak Lemma 49 04 is then also a quadratic irrational Proof 12 is a quadratic irrational Then7 is d a quadratic irrational a quadratic irrational dab i acdbn c c ls m quadratic irrational c a 7 limo a b i a2 7 bzn Yes Therefore7 by induction Diophantine equations Have some polynomial equations7 in some variables 2y22272y2273y32372y222w72y222w2t 27 Theorem 50 It is impossible to analyze a general Diophantine equation Proof The dif culty of this problem is too much for us D Theorem 51 IfA is a formal math conjecture then there epists a polynomial pAd1wk 0 computable directly from A that has solutions in Z i A is true Theorem 52 IfA is a formal computer program then there epists a pA1n whose positive values 1 dn 6 Z are the output of A We have 2 y2 22 where Luz E Z These are called Pythagorean triples Without loss of generality lets just consider Luz gt 0 We want gcdxyz 1 because otherwise this is just trivial The triples with gcddyz 1 are called primitives A plan n127n22n1 sometimes that odd number on the right are squares Examples 42 32 52 52 52 132 242 72 252 402 92 412 General formula z m2 7 n2 y 277m and z m2 n2 where gcdm n 1 36 Pythagorean triples 2 y2 22 was studied by various ancient civilizations Formulae for Pythagorean triples d m2 7 n2 y2mnzm2n2 Now Fermat proposed x y 2 For each xed n it7s Diophantine Very different behavior for different n with something in common Theorem 53 Fermat s Last Theorem There are no non trivial integer solutions to x y 2 Have fun with the proof Theorem 54 Fermat did solve this though 4 14 24 has no non triuial solutions If n 1 z y 2 then that7s easy If n 2 2 y2 22 that7s doable Just Pythagorean triples Let n ab Then Mb gay7 2 17 This is a special case of 17 yb 2b This reduces the cases to primes of power 4 and n is prime 28 No solutions to a2 b2 02 7 There7s also no solutions to mod 8 i no solutions Let7s look at x2 y2 22 and gcdy 1 Quadratic solutions of mod 4 is 01 With 0 0 0 and 1 1 27 they arent interesting 1 0 1 0 1 Without loss of generality7 z is odd and y is even Using the formulae of pythagoren triples 2 m2 7 n22 m4 7 27712712 n4 yz 47712712 22 m2 n22 m4 27712712 714 2 y2 lf gcdmn d7 then dzlzy We want gcdmn 17 then gcdy 1 Say gcdmn 1 Say ply 2mm lfp 27 then p Xx 7712712 and z 21 mod 2 If plm7 then p X71 so z E n2 i 0 mod p Theorem 55 If x2 y2 22 with gcdy 1 and 21y then x m2 7 712 y 277m 2 m2 712 Proof Let y2 22 7 x2 z 7 Claim gcdz 7 x z z 2 First of all7 we know that 2 Xxx so it is at least 2 gcdz z z 7 s gcdz z 22 lfp is odd 7 227 then plz Then7 p Then7plzz 12 xzz7x z2 27 477 2 2 2 zz 27 lt2 lt 2 gtlt 2 gt By unique factorization7 my m2 and Z n2 So7 we have the following three equations 2 mznz 242 m2 27m n2 First equation gets you y If we add the latter two equations7 you get 2 If we subtract the latter two equations7 you get z 29 1 39 Pythagorean triples and Fermat s last theorem The solution x m2 7 712 y 277m 2 m2 712 gcdmn 1 m and n are not both odd and gcdy 1 If dlmn then let m n 1 z 72 y 1712 and 2 1 If mn are both odd m MT 71 x g y g and 2 Suggestive alternate formula x y mz n2 z 1m 271 m 7 m Of cial lame full solution x km2 7 n2 2kmnz km2 712 Another proof Proof 2 y2 22 is a homogenous Diophantine equations Solutions in Z lt gt solutions in Q lt gt solutions to 2 y2 1 D Open Problem Are Q Diophantine equations computationally universal andor mathematically universal like Z dio phantine equations are Example 2y222 H 2y21 2 2 324252 H 1 What is the solution to 2 y2 1 A unit circle centered at the origin Suppose that z and y are rational Suppose 1 form a line between 01 and y is the slope of the line rational Yes In fact the slope s is lf 5 E Q then my 6 Q2 because you have a quadratic equation such that one solution 01 is rational x2y21andyzs1so 2sx12 1 z252x22511 We then have 1 52x 25 0 so z Thenysx1i Let s then x 33 and y Although a few cosmetic errors we can x it to look like what were looking for This is the same idea that works for any diophantine equations with any quadraticxyz 0 which is homogenous and such that you know one solution Example 3x24y2 722 A solution 111 and tgiis is homogenous since all the terms are quadratic 3x2 4y2 7 forms the ellipse s E Q lt gt my 6 Q2 A case of Fermat s last theorem 4 y4 24 has a no non trivial solutions Proved by 77in nite descen 77 Solution a smaller solution This is a contradiciton with a form of induction What we actually show by induction is 4 14 22 and 411 y2 24 have no solutions 311 Theorem 56 4 14 24 has no non trivial solutions Hard to prove alone Theorem 57 4 14 22 and 4x4 y2 24 has no trivial solutions Proof is by 77in nite descen 77 ie solution implies a smaller solution Basically7 its a contraction in the form of an induction or 77 attack the smallest counterexample These are Pythagorean tripes7 27y272 and 2x27y722 ln 4 14 22 can we make 27y2 z a primitive triple gcd2y2 1 lt gt gcdy2z 1 lt gt gcdz2z 1 lt gt primitive lf gcdx2y2 6127 then x g y g and 2 1 Therefore7 x27y272 is primitive All primitive pythagoren triples are oddz 616712 oddz Let7s switch Ly if necessary 2 m2 7 n2 y2 277m 2 m2 n2 where gcdmn 1 and one of m7 n is odd7 the other even and z is odd We also know that n2 x2 m2 is another pythagorean triple7 so n has to be even and m is odd Then7 yz 277m That means that m 1 2n This implies m 52 and n 2t2 Combining them7 I get 4t2 x2 s4 where mz39nz7 t s lt m nzy Say we have 4x4 y2 24 Could 2 be even and x be odd Lets say no If gcdz d gt 17 then let x g 2 1 by induction7 so z 1 2 so x2 1 22 and 2x2 1 22 So7 2x27y722 is primitive by induction Now7 we know that 2x2 277m y m2 7 n2 2 m2 n2 Then7 p2 mn If m l n7 then m 52 and n t27 so 22 52 t2 Gaussian integers Motivation If x2 y2 22 then x iy x iy 22 If we could say xiy l xiiy7 then presumably xiy min27 which is the formula for Pythagorean triples What does the relative prime for complex integers mean De nition 58 Let Z be the set of integers Let C Zli be the Gaussian integers Gaussian integers are x iylxg E Z 5 2 i2 7 i in Zi 5 is not a Guassian prime 3 i73i is not a reasonable factorization 3 does not factor to 77shorter77 numbers It is a Gaussian prime De nition 59 Z Z i 7i are called units Ifz E Zli does not factor ecccept as 2 u 2 then it is a Gaussian prime Theorem 60 Z Zi have unique factorization 2 The primes are p E Z such that p 3 mod 4 and a it where a2 b2 p E 1 mod 4 313 Gaussian integers De nition 61 Ifu E Z i has a reciprocal u 1 E Zli then it s a unit So7 which elements is that De nition 62 Ifz E Zli Nz le 2 12 E Z where z z iy Note Nz is the number theorists norm and is the analyst norm M Nz0lt z0 m as Gaussian integers because Nz z E x 7 iy Note 2 E Zi gtE E Zi m N2122 N21N22 Theorem 63 Unique Factorization of Gaussian integers lel have unique factorization mto Gaussian primes In fact ifu is a unit 2 uz z and uz are associates Associate primes are equivalent in the sense of factorization Example ls 2 square free in ZM 2 1z 17 Are there repeats Yes 1 7 239 721 239 Therefore 2 z1 239 Therefore 2 is not square free Why are we caring about units In the past we can just restrict everything to positive numbers Now we cant Why Z has unique factorization For uniqueness division with remainders which led to euclidean algorithm which led to primality lemma which led to unique factorization All of our implications are inevitably provided you get it started As for the existence you have this if elements have a size which decreases when you factor Does Nz have a positive integer size such that if z ab where ab are not units so that Na Nb lt Nz7 Yes Nz NaNb and NaNb 2 2 Example 2 1 z391 7239 where N2 4 and N1z39 2 Division with remainders We want the following Given ab E lel a qb r such that Nr lt Nb In the Cartesian coordinates multiplying by b dilates by lbl and rotates by the angle of b which is known as Argb Example b 2 239 316 ZM has division with 77good77 remainders a qb 7 with Nr lt Nb 1 are not unique but that7s ok


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Jim McGreen Ohio University

"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."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.