### Create a StudySoup account

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

Already have a StudySoup account? Login here

# FOUNDATIONS OF ARITHMETIC M 316K

UT

GPA 3.67

### View Full Document

## 83

## 0

## Popular in Course

## Popular in Mathematics (M)

This 12 page Class Notes was uploaded by Reyes Glover on Sunday September 6, 2015. The Class Notes belongs to M 316K at University of Texas at Austin taught by Staff in Fall. Since its upload, it has received 83 views. For similar materials see /class/181525/m-316k-university-of-texas-at-austin in Mathematics (M) at University of Texas at Austin.

## Reviews for FOUNDATIONS OF ARITHMETIC

### 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/06/15

NUMBER THEORY QUESTIONS JD MIRELES JAMES 1 QUESTIONS FROM LAST Two CLASSES Question 11 For n gt 2 are there nonzero solutions to the equation a b c Question 12 Is there a biggest prime number Or is the set of prime numbers in nite Question 13 If I hand you an even number k and the number I hand you is bigger than 2 can you nd prime numbers p1 and p2 so that P1 P2 k7 p1 p2 is allowed Now that you have worked on each of these a little7 which do you think are true and which do you think are false If you had to work on one over the others7 which problem do you think would be the most dif cult Which would be the easiest Date July 30th 2008 1991 Mathematics Subject Classi cation math Key words and phrases math all J D MIRELES JAMES 2i INFINITE PRIMES Theorem 21 Euclid7s Prime Number Therorem The set of prime numbers is in nite This theorem was proved by the Greek mathematician Euclid in around 300 BC The Elements The proof relies on a fact known as the fundamental theorem of arithmetic which we will discuss in the next few days This theorem and its proof is the kind of thing the any undergraduate student of mathematics should know off the top of their head Even though there are in nitely many primes nding them can be very dif cult As many of you pointed out last time there seem to be less and less primes as you go to higher and higher numbers In fact there is a theorem know as The Prime Number Theorem which tells in terms of probability how many prime numbers you are likely to have if you consider the set of numbers 1 23i i i N As you take bigger and bigger N the likeliness of nding more primes grows very slow yi Large Prime numbers are used to encrypt data think you bank accounts or email accounts or any private electronic data i The largest known prime number was discovered on August 23 of this year 2008 The number can be written as 243gt112gt509 7 1 If you expand this number into decimal notation it will have 12978189 digitsi The number was found by The Great Internet Mersenne Prime Search NUMBER THEORY QUESTIONS 3 3i SOLUTIONS WITH n gt 3 Theorem 31 Fermatls Last Theorem If n is a natural number greater than 2 then the equation has no anbncn nonzero integer solutions For n 2 the problem is related to the Pythagorean Theorem which relates the squares of sides of a right triangle Since similar triangles have similar ratios of sides if you know one solution to the equation for n 2 then you can nd in nitely many solutions For n gt 2 the problem was posed by the French Mathematician Pierre de Fermat in the year 1637 Fermat claimed to have found a proof of the theorem but died without passing it on The question remained unsolved for 357 years and became one of the most famous and longstanding problems in all of mathematics In 1995 the British mathematician Andrew Wiles produced the rst correct proof of the theoremi His proof is 109 pages of very dif cult mathematics and took more than seven years to complete An elementary proof has yet to be found J D MIRELES JAMES 4 AN OPEN PROBLEMM Theorem 41 The Goldbach Conjecture Can every even number k gt 2 be expressed as the sum of primes The question was proposed by the Prussian mathematician Christian Gold bach in a letter to Swiss mathematician Leonhard Euler in the year 1742 This question has remained unsolved for the last 266 years in spite of much work by many mathematicians The Goldbach Conjecture is currently one of the most famous outstanding problems in number theory The conjecture has been veri ed by computers for k lt 1018 Nevertheless no number of examples can ever prove a theoremi They only increase our con dence in the truth of the conjecture For Fermat7s last theorem there was a crescendo of work starting in the 1950 s leading up to the proof The Goldbach conjecture seems less close to resolution Nevertheless the question might be settled this week or might take another three hundred years A few minutes on the internet will show you that there are many attempted proofs of the conjecture or people on line who have claimed to prove it NUMBER THEORY QUESTIONS 5 5 PROJECTS Project Description Report At least ve pages double spaced Pick a topic from be ow Histon39cal Projects Write a report on the history of Fermatls Last Theoremi Should include biographical sketches of important gures involved Discussion of important events in the life of the problemi Some discussion of the problem itself As to the solution I donlt expect any of us to understand it myself included and l donlt think the report should contain any information you donlt understand On the other hand there is a lot a information on the human side of the proof Write a report on the Goldbach conjecturei Similar to above Write a report on the Twin Prime Conjecture Similar to above Report on Women in the history of mathematics Write a repore on Euclid and The Elements There are supprising connec tions between the history of mathematics and the history of philosophy in general A lot of this is tied up in the history of The Elements There are lots of interesting directions such a project could go in Report on the Pythagorean Cult Attempts to legislate the value of 7s A de nitive report with references including nding actual bills and discussion Report on the Prime Number Theoremi Report on Paul Erdosi Mathematical Projects Three proofs of Pythagorean Theoremi Proof that there are in nitely many primes Proof that the square root of two is irrationali Report on Prime Numbers in encryptioni Report on the Fundamental Theorem of Ari themetici 6 JD MIRELES JAMES 6 THE MOST IMPORTANT THEOREM WE WILL DISCUSS THIS SEMESTER Theorem 61 The Fundamental Theorem of Arithmetic Every natural number greater than 1 is either prime or can be factored uniquely into a product of prime numbers The list offactors is unique up to order The theorem says that every number can be represented as a product of primesl To put it another way if I hand you a whole number k gt I you can always hand me back a list of primes m l l l pn so that h p1 gtlt gtlt pn The statement about uniqueness just means that if I give the same number k to two different people they will both come up with the same list of primes as long as I don7t mind if their lists are in different orders I can predict what will be on everyones list but not in what order they will choose to write the list Examples 0 42X2l Soforh4thelist is p12p22l o 21 3 X 7 So the list of prime factors is 3 7 Someone else might choose to write this as 73 but it s still the same list 0 30 2 X 3 X 5 and its list is just 235 0 ll l X 11 The list for a prime is just itself you leave one off the list NUMBER THEORY QUESTIONS 7 7i PRIME FACTORIZATION EXERCISES Find the prime factorization of each of the following numbers 1 suggest working Without a calculator7 as this is good practice for the nal exam 37 105 152 200 201 its not prime 261 not prime 288 323 616 1001 not prime 1183 not prime 1734 Question Here is a list of prime numbers 2737 5 Find some numbers that have all three of these as prime factorsi Can you nd a number Which is guaranteed not to have any of these as prime factors Try the same problem With the list 37 7 11 Question Suppose I hand you a list 101111 7pn of prime numbers Can you produce a number Whose prime factors cannot be any of the numbers on the list 8 JD MIRELES JAMES 8 THE NEW LIST TRICK Last time we worked on the following problem Question 81 The New List Problem Suppose you are given a list 101102 r i i 7pn of primes How can you produce a new number Knew not already on the list with the property that either Knew is prime or the prime factors of Knew are not in the original list In other words either Knew or any of its prime factors give you a prime number you did not have before Some students proposed the following solution to the question Take all the numbers on the list and multiply them together7 then add one This gives Knewp1Xp2X Xpn1 One nice thing about this method is that no matter what list you are given7 you always do exactly the same thing NUMBER THEORY QUESTIONS 9 9 LIST TRICK EXERCISES Show that the trick works on the following lists Compute Knew for each list and then compute the prime factorization of Knew ee wether or not any of the prime factors of Knew are on the original list Again I suggest doing these by hand 0 2 2 2 27 3 o o o o o o o 3355 o o o o o 0 35 711 Question 91 Now that you believe the trick always works can you prove it does Try to prove it algebraically for the list a b with a b both prime you are trying to prove that neither a nor b can possibly divide Knew for this list How about the list a b c with a b c all prime Once you can do these it s easy to do p1p2 pn Question 92 With what you know now you are ready to prove Euclid s prime number theorem Give it a shot Prove that there are in nitely many primes You can do this by proving that any nite list of primes is always incomplete 10 JD MIRELES JAMES 10 NUMBER CIRCLES VERSUS NUMBER LINES The idea behind a number Circle is to cut the natural numbers off at some point and Wrap the line around on itself to make a Circle Then we can project counting and addition onto this Circle see the pics and notation on the board Question 101 Draw the mod number circle Compare counting to ten on the number line and on the mod circle What are 0 8 mod 2 o 9 mod 2 o 10 mod 2 o 12 mod 2 o 23 mod 2 o 24 mod 2 o 25 mod 2 0 100000 027mod2 0 23599 472 mod2 What does the mod2 value of a natural number tell you about the number In other words if I tell you that zmod2 1 what do you know about 1 Similarly what does zmod2 0 tell you about 1 Question 102 Draw the mod 7 mod 10 and mod 11 number circles Compare the number line and the number circles for values on the number line up to at least 25 What are 20 mod 7 20 mod 10 and 20 mod 119 Compute each of z mod7 1011 for 1 equal to each of the following o 35 37 42 49 5o 55 50 7o 77 78 79 100 101 111 112 113 114 115 145 147 153 154 155 500 555 Question 103 What does the value ofzmodn tell you about 1 Question 104 Experiment with addition in a couple of number circles 0 Try working 2 2 mod3 5 5 mod7 7 6 mod11 and 6 6 mod2 0 Make up some more problems to work until you feel pretty comfortable with this kind of addition Question 105 Do you think that the following equations are true or false Back up your answer in every case with a bunch of examples Can you explain why your answer is correct Think about how you could prove your answer 0 ab mod3 amod3 bmod3 o ab mod4 amod4 bmod4 o ab modn amodn bmodn o a X b mod3 amod3 gtlt bmod3 o a X b mod4 amod4 gtlt bmod5 o a X b modn amodn gtlt bmodn a X b c mod5 amod5 gtlt bmod5 amod5 gtlt cmod5 a X b c mod6 amod6 gtlt bmod6 amod6 gtlt cmod6 o o o a X bcmodn amodn gtlt bmodnamodn gtlt cmodn NUMBER THEORY QUESTIONS 11 11 THE LITTLE PUBLIC KEY77 ENCRYPTION SYSTEM Suppose that I am a bank7 and you are a customer You want to be able to check you bank ballance online7 or at an ATM Everyone will know and use the same web address and the same ATMs Your information if protected by two facts the data is encrypted7 and only you know your password The encryption of data involves prime numbers and the fact that large compisite numbers are very hard to factor The little public key77 system is a simpli cation of an encryption system called RAS7 which illustrates that information can be encoded and decoded by people whos only secret is that they both know the prime factorization of a large composite number De nition 111 Public Key Choose very large prime numbers p1pn Form their product M p1 gtlt gun This is the public key which everyone will now De nition 112 PassKey Everyone is given a diferent passkey pi Only you know your passkey De nition 113 DecoderKey Your decoderkey is L Mpi Now I send you a message The message is a sequence of big natural numbers7 say A7 B7 C7 D Each of these has as many digits as M To decode the message you compute A mod 4 B mod 4 Cmod L D mod 4 Since only you know 4 only you can decode the message 12 JD MIRELES JAMES Example Suppose that there is only one customer and our public key is M 6 this is way too small but this example is just to see the steps Then M has prime factorization 6 2 X 3 If your passkey is p 2 then your decoder key is L 6 2 3 Now I send you your encrypted account ballance The message is a binary number represebnting your account ballance in binary You have to decypher the message and convert to base ten to know your ballance 463 You decode this as 4mod3 6 modS SmodS 1 0 0 100 Then you decimal account ballance is four dollars Question 114 How do I encode the data Hint I know your encoderkey So I can make a number linecircle table for the mod 5 number circle Question 115 Pick a bigger composite number for the public key M Pick a key and produce the decoder Try encrypting some binary data Trade with another student Make sure you teel them what key you were using See if you can decode their data

### 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

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

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

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

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