Topic 1: Combinatorics & Probability

Topic 1: Combinatorics & Probability

Topic 2: Number Theory Dr J Frost ([email protected]) www.drfrostmaths.com Last modified: 12th October 2015 Slide Guidance Key to question types: SMC Senior Maths Challenge Uni Questions used in university interviews (possibly Oxbridge). www.ukmt.org.uk The level, 1 being the easiest, 5 the hardest, will be indicated.

BMO British Maths Olympiad Those with high scores in the SMC qualify for the BMO Round 1. The top hundred students from this go through to BMO Round 2. Questions in these slides will have their round indicated. MAT Maths Aptitude Test Admissions test for those applying for Maths and/or Computer Science at Oxford University. University Interview Frost

A Frosty Special Questions from the deep dark recesses of my head. Classic Classic Well known problems in maths. STEP STEP Exam Exam used as a condition for offers to universities such as Cambridge and Bath. Slide Guidance ?

Any box with a ? can be clicked to reveal the answer (this works particularly well with interactive whiteboards!). Make sure youre viewing the slides in slideshow mode. For multiple choice questions (e.g. SMC), click your choice to reveal the answer (try below!) Question: The capital of Spain is: A: London B: Paris C: Madrid Topic 2: Number Theory Part 1 Introduction a. Some History b. Divisibility Tricks

c. Coprimality d. Breaking down divisibility problems Part 2 Factors and Divisibility a. Using the prime factorisation i. Nearest cube/square ii. Number of zeros iii. Number of factors b. Factors in an equality c. Consecutive integers Topic 2: Number Theory Part 3 Diophantine Equations a. Factors in an equality (revisited) b. Dealing with divisions c. Restricting integer solutions Part 4 Modular Arithmetic a. Introduction b. Using laws of modular arithmetic c. Useful properties of square numbers c. Multiples and residues d. Playing with different moduli

Topic 2: Number Theory Part 5 Digit Problems a. Reasoning about last digit b. Representing algebraically Part 6 Rationality Part 7 Epilogue Topic 2 Number Theory Part 1: Introduction What is Number Theory? Number Theory is a field concerned with integers (and fractions), such as the properties of primes, integer solutions to equations, or proving the irrationality of /e/surds.e/e/surds.surds. How many zeros does 50! have? What is its

last non-zero digit? How many factors does 10001000 have? Are there any integer solutions to a3 + b3 = c3? Prove that the only non-trivial integer solutions to ab = ba is {2,4} Who are the big wigs? Euclid (300BC) Better known for his work in geometry, but proved there are infinitely many primes. Euclids Algorithm is used to find the Greatest Common Divisor of two numbers. Fermat (1601-1665) Most famous for posing Fermats Last Theorem, i.e. That has no integer solutions for , and when . Also famous for Fermats Little Theorem (which well see), and had an

interest in perfect numbers (numbers whose factors, excluding itself, add up to itself). Euler (1707-1783) Considered the founder of analytic number theory. This included various properties regarding the distribution of prime numbers. He proved various statements by Fermat (including proving there are no integer solutions to ). Most famous for Eulers Number, or e for short and Eulers identity, . Who are the big wigs? Lagrange (1736-1813) Proved a number of Eulers/Fermats theorems, including proving that every number is the sum of four squares (the Four Square Theorem). Dirichlet (1805-1859) Substantial work on analytic number theory. e.g. Dirichlets Prime Number Theorem: All arithmetic sequences, where the initial term and the common difference are coprime, contain an infinite number of prime numbers.

Riemann (1826-1866) The one hit wonder of Number Theory. His only paper in the field On the number of primes less than a given magnitude looked at the density of primes (i.e. how common) amongst integers. Led to the yet unsolved Riemann Hypothesis, which attracts a $1m prize. Who are the big wigs? Andrew Wiles (1953-) He broke international headlines when he proved Fermats Last Theorem in 1995. Nuf said. Is 1 a prime number? Vote No Yes Vote Euclids Fundamental Theorem of Arithmetic, also known as the Unique Factorisation Theorem, states that all positive integers are uniquely expressed as the product of primes.

Assume that 1 is a prime. Then all other numbers can be expressed as a product of primes in multiple ways: e.g. 4 = 2 x 2 x 1, but also 4 = 2 x 2 x 1 x 1, and 4 = 2 x 2 x 1 x 1 x 1, and so on. Thus the Fundamental Theorem of Arithmetic would be violated were 1 a prime. http://primes.utm.edu/notes/faq/one.html provides some other reasons. (Note also that 0 is neither considered to be positive nor negative. Thus the positive integers start from 1) Divisibility Tricks How can we tell if a number is divisible by... 2 3 4 5 6 7 Last number is even. ? Digits add up to multiple of 3. e.g: ?

1692: 1+6+9+2 = 18 Last two digits are divisible by 4. e.g. ? 143328 Last digit is 0 or 5. ? Number is divisible by 2 and 3 (so use tests for 2 and 3). ? There isnt really any trick that would save time. You could double the last digit and subtract it from the remaining digits, and see if the result is divisible by 7. e.g: 2464 -> 246 8 = 238 -> 23 16 = 7. But youre only removing a digit each time, so you might as well long divide! ? 8 9 10 11 Last three digits divisible by 8.

? Digits add up to multiple of 9. ? Last digit 0. ? When you sum odd-positioned digits and subtract even-positioned digits, the result is divisible by 11. ? e.g. 47949: (4 + 9 + 9) (7 + 4) = 22 11 = 11, which is divisible by 11. 12 Number divisible by 3 and by 4. ? Notation

28 This means 2 does not divide 9. 2 9 5 is a factor of 15. This means 2 divides 8. 15 is divisible by 5. Notation This is NOT a coordinate! It means the Greatest Common Divisor of 15 and 10.

( 15,10 ) =5 The Lowest Common Multiple of 6 and 8. ( 6,8 )=24 True or false If and , then is it the case that ? False True If and , then is it the case that ? False True Take 12 for example. Its divisible by 4 and 6, but

not by 24. In general, if a number is divisible by a and b, then the largest number its guaranteed to be divisible by the Lowest Common Multiple of a and b. LCM(4,6) = 12. Coprime If two numbers a and b share no common factors, then the numbers are said to be coprime or relatively prime. The following then follows: Coprime? 2 and 3? No True 5 and 6?

No True 10 and 15? No True Breaking down divisibility problems We can also say that opposite: If we want to show a number is divisible by 15: ...we can show its divisible ? by 3 and 5. But be careful. This only works if the two numbers are coprime:

If we want to show a number is divisible by 8: ...we can just show its divisible by 4 and 2? No: LCM(2,4) = 4, so a number divisible by 2 and 4 is definitely divisible by 4, but not necessarily?divisible by 8. Breaking down divisibility problems Key point: If were trying to show a number is divisible by some large number, we can break down the problem if the number were dividing by, n, has factors a, b such that n = ab and a and b are coprime, then we show that n is divisible by a and divisible by b. Similarly, if n = abc and a, b, and c are all coprime, we show its divisible by a, b and c. If we want to show a number is divisible by 24: We can show its divisible by 3 and ? 8 (Note, 2 and 12 wouldnt be allowed because theyre not coprime. That same applies for 4 and 6) Which means wed have to show the number has the following properties: 1. Its last 3 digits are divisible by 8. ? a multiple of 3.

2. Its digits add up to Breaking down divisibility problems Question: Find the smallest positive integer which consists only of 0s and 1s, and which is divisible by 12. Use what you know! I can break divisibility tests into smaller ones for coprime numbers. Answer: 11100 ? A number divisible by 12 must be divisible by 3 and 4. If divisible by 4, the last two digits are divisible by 4, so most digits must be 0. If divisible be three, the number of 1s must be a

multiple of 3. For the smallest number, we have exactly 3 ones. IMO Maclaurin Hamilton Cayley Breaking down divisibility problems Explain why and are coprime for any positive integer k. Answer: Suppose k had some factor q. Then k+1 must have a remainder of 1 when divided?by q, so is not divisible by q. The same reasoning underpins Euclids proof that there are infinitely many primes. Suppose we have a list of all known primes: p 1, p2, ... pn. Then consider one more than their product, p1p2...pn + 1. This new value will always give a remainder of 1 when we divide by any of the primes p 1 to pn. If its not divisible by any of them, either the new number is prime, or it is a composite number whose prime factors are new primes. Either way, we can indefinitely generate new prime numbers.

Coprime If is odd, will and be coprime? Answer: No. Because k-1 and k+1 will be contain ? a factor of 2. If is even, will and be coprime? Answer: Yes. If a number d divides k-1, then the remainder will be 2 when k+1 is divided by d. Thus the divisor could?only be 2, but k-1 is odd. Therefore there can be no common factor. These are two very useful facts that Ive seen come up in a lot of problems. Well appreciate their use more later: 1. and are coprime for any positive integer . 2. and are coprime if is even. Topic 2 Number Theory

Part 2: Factors and Divisibility Using the prime factorisation Finding the prime factorisation of a number has a number of useful consequences. 360 = 2 x 3 x 5 3 ? 2 Well explore a number of these uses... Using the prime factorisation Handy Use 1: Smallest multiple thats a square or cube number? 360 = 2 x 3 x 5 3

2 ? Smallest multiple of 360 thats a perfect square = 3600 If the powers of each prime factor are even, then the number is a square number (known also as a perfect square). For example 24 x 32 x 52 = (22 x 3 x 5)2. So the smallest number we need to multiply by to get a square is 2 x 5 = 10, as well then have even powers. Using the prime factorisation Handy Use 1: Smallest multiple thats a square or cube number? 360 = 2 x 3 x 5 3 2 ? Smallest multiple of 360 thats a cube = 27000 If the powers of each prime factor are multiples of three, then

the number is a cube number. For example 23 x 33 x 53 = (2 x 3 x 5)3. So the smallest number we need to multiply by to get a square is 3 x 52 = 75. Using the prime factorisation Handy Use 2: Number of zeros on the end? 2 x3 x5 7 2 4 Q1) How many zeros does this number have on the end? Answer: 4. 27 x 32 x 54 = 23 x 32 x (2 x 5)4 ? = 23 x 32 x 104 Q2) Whats the last non-zero digit? Answer: Using the factors we didnt combine to make

2-5 pairs (i.e. factors of 10),?we have 23 x 32 left. This is 72, so the last non-zero digit is 2. Using the prime factorisation Handy Use 2: Number of zeros on the end? What is the highest power of 10 thats a factor of: 50! 1000! Answer: 12 50! = 50 x 49 x 48 x ... We know each prime factor of 2 and 5 gives us a power of 10. Theyll be plenty of factors of 2 floating around, and less 5s, so the number of 5s give us ? the number of pairs. In 50 x 49 x 48 x ..., we get fives from 5, 10, 15, etc. (of which theres 10). But we get an additional five from multiples of 25 (of which theres 2). So thats 12 factors of 10 in total. Answer: 249 Within 1000 x 999 x ... , we get prime factors of 5 from each multiple

of 5 (of which theres 200), an additional 5 from each multiple of 25 ? 5 from each multiple of 125 (of (of which theres 40), an additional which theres 8) and a final five from each multiple of 625 (of which theres just 1, i.e. 625 itself). Thats 249 in total. Using the prime factorisation Handy Use 2: Number of zeros on the end? What is the highest power of 10 thats a factor of: In general, n! log5 n gives us power of 5 that results in n. So rounding this down, we get the largest power of 5 that?results in a number less than n. x is known as the floor function and rounds anything inside it down. So log5 1000 = 4. Then if k is the power of 5 were finding multiples of, theres n / 5k of these multiples (after we round down). Using the prime factorisation For how many positive integer values of k less than 50 is

it impossible to find a value of n such that n! ends in exactly k zeros? A: 0 B: 5 D: 9 E: 10 C: 8 When n! is written in full, the number of zeros at the end of the number is equal to the power of 5 when n! is written as the product of prime factors. We see that 24! ends in 4 zeros as 5, 10, 15 and 20 all contribute one 5 when 24! is written as the product of prime factors, but 25! ends in 6 zeros because 25 = 5 5 and hence contributes two 5s. So there is no value of n for which n! ends in 5 zeros. Similarly, there is no value of n for which n! ends in 11 zeros since 49! ends in 10 zeros and 50! ends in 12 zeros. The full set of values of k less than 50 for which it is impossible to find a value of n

such that n! ends in k zeros is 5, 11, 17, 23, 29, 30 (since 124! ends in 28 zeros and 125! ends in 31 zeros), 36, 42, 48. SMC Level 5 Level 4 Level 3 Level 2 Level 1 Using the prime factorisation Handy Use 3: Number of factors? 72576 = 2 x 3 x 7 7 4 A factor can combine any number of these prime factors together. e.g. 22 x 5, or none

of them (giving a factor of 1). We can use between 0 and 7 of the 2s to make a factor. Thats 8 possibilities. Similarly, we can have between 0 and 4 threes. Thats 5 possibilities. And we can either have the 7 or not in our factor. Thats 2 possibilities. So theres 8 x 5 x 2 = 80 factors Using the prime factorisation Handy Use 3: Number of factors?

In general, we can add 1 to each of the indices, and multiply these together to get the number of factors. So above, there would be factors. Using the prime factorisation Handy Use 3: Number of factors? How many factors do the following have? 50? = 2 x 52 ? so 2 x 3 = 6 factors. 10100? = (2 x 5)100 = 2100 x 5100

So 1012?factors = 10201 factors. 200? =2 x5 ? so 4 x 3 = 12 factors. 20032003? 3 2 (Note: 2003 is prime) This is already primefactorised,?so theres 2004 factors. Using the prime factorisation

Question: How many multiples of 2013 have 2013 factors? A: 0 B: 1 C: 3 D: 6 E: Infinitely many Hint: 2013 = 3 x 11 x 61 Use the number of factors theorem backwards: If there are 2013 factors, what could the powers be in the prime factorisation? Solution: Firstly note that any multiple of 2013 must have at least powers of 3, 11 and 61 in its prime factorisation (with powers at least 1). If there are 2013 factors, then the product of one more than each of the powers in the prime factorisation is 2013. e.g. We could have 32 x 1110 x 6160, since (2+1)(10+1)(60+1) = 2013. Theres 3! = 6 ways we could arrange these three powers, which all give multiples

of 2013. Our multiple of 2013 cant introduce any new factors in its prime factorisation, because the number of factors 2013 only has three prime factors, and thus cant be split into more than three indices. Int Kangaroo Pink Grey Factors in an equality We can reason about factors on each side of an equality . What do we know about and ? 3 =8 Answer: If the LHS is divisible by 3, then so must the RHS. And since 8 is not divisible?by 3, then k must be. By a similar argument, n must be divisible by 8. Factors in an equality In general, if we know some property of a number, it

can sometimes help to replace that number with an expression that represents that property. This skill becomes hugely important when considering integer solutions for equations. is even: Let for some integer is odd: Let ? is a multiple of 9: Let ? only has prime factors of 3: Let ? is an odd square number: If and is odd, must ? also be odd. So Factors in an equality

Question: Show that has no integer solution for . Answer: Since the LHS only has prime factors of 2, then so must the RHS. Therefore let for some integer . Then and equating indices,? . But the RHS is divisible by 3 while the LHS is not, leading to a contradiction. Factors in an equality Question: If , then what can we say about and ? (Recall: and are coprime) Answer: If k and k+1 are coprime, they share no factors, so the prime factors on the LHS must be partitioned into two, depending whether they belong to k or k+1. In n2, each prime factor appears twice, so they must both belong to either k or k+1 (but cant be in both). So far, both k and k+1 will both be square, ? because each prime factor comes

in twos. This just leaves the 3, which is either a factor of k or k+1. Therefore, one of k and k+1 is three times a square, and the other a square. (An interesting side point: Finding possible n is quite difficult. Using a spreadsheet, the only valid n I found up to 10,000 were 2, 28, 390 and 5432.) Divisibility with consecutive integers Every other integer is divisible by 2. 1 2 3 4 5 6

7 8 Every third integer is divisible by 3. 1 2 3 4 5 6 7

8 Every fourth integer is divisible by 4. 1 2 3 4 5 6 7 8 An obvious fact that can aid us in solving less

than obvious problems! Divisibility with consecutive integers Which of the following is divisible by 3 for every whole number x? A: x3- x B: x3 -1 3 D: x +1 E: x3 +x C: x3 Since x3 x = x (x2 1) = (x 1) x (x + 1), x3 x is always the

product of three consecutive whole numbers when x is a whole number. As one of these must be a multiple of 3, x3 x will be divisible by 3. Substituting 2 for x in the expressions in B,C and E and substituting 3 for x in the expression in results in D numbers which are not divisible by 3. (Note: Well revisit this problem later when we cover modulo arithmetic!) SMC Level 5 Level 4 Level 3 Level 2 Level 1 Divisibility with consecutive integers Let n be an integer greater than 6. Prove that if n-1 and n+1 are both prime, then n2(n2 + 16) is divisible by 720. Solution: As n-1 and n+1 are prime, n must be divisible by 2

(since n>6). Thus n2(n2 + 16) is divisible by 24, as n4 and 16n2 both are. One of n-1, n and n+1 must be divisible by 3, but since n-1 and n+1 are prime, n must be divisible by 3. Therefore n 2(n2 + 16) must be divisible by 9, as n2 is. One of n-2, n-1, n, n+1 and n+2 ? are divisible by 5. n-13 and n+1 cant be as theyre prime. Therefore (n-2)n(n+2) = n 4n is a multiple of 5. We now need to somehow relate this to n2(n2 + 16) = n4 + 16n2. If n3 4n is divisible by 5, then n4 4n2 is, and n4 4n2 + 20n2 is because 20n2 is clearly divisible by 5. Therefore n2(n2 + 16) is divisible by 5. Thus, n2(n2 + 16) is divisible by 24 x 32 x 5 = 720. Use what you know! If n-1 and n+1 are both prime, I can establish properties

about ns divisibility. 720 has a factor of 5. What expression can I form that we know will be divisible by 5? BMO Round 2 Round 1 Topic 2 Number Theory Part 3: Diophantine Equations What is a Diophantine Equation? An equation for which were looking for integer solutions.

Some well-known examples: xn + yn = zn 3x + 4y = 24 When n=2, solutions known as Pythagorean triples. No solutions when n>2 (by Fermats Last Theorem). Linear Diophantine Equation. Well see an algorithm for solving these. Erdos-Staus Conjecture states that 4/n can be expressed as the sum of three unit fractions (unproven). x2 ny2 = 1 Pells Equation. Historical interest because it could be used to find approximations to square roots. e.g. If solutions found for x2 2y2 = 1, x/y gives an approximation for 2

Factors in an equality To reason about factors in an equality, it often helps to get it into a form where each side is a product of expressions/e/surds.values. Example: How many positive integer solutions for the following? ( 6 )( 10)=15 Answer: 6. Possible (x,y) pairs are (7, 25), (9, 15), ? (11, 13), (21, 11), (3, 5), (1, 7) The RHS is 15, so the multiplication on the LHS must be 1 x 15, 3 x 5, 5 x 3, 15 x 1, -1 x -15, -3 x -5, etc. So for the first of these for example, x-6=1 and y-10=15, so x=7 and y=25. Make sure you dont forget negative factors. Forming a Diophantine Equation You should try to form an equation where you can reason about factors in this way!

Question: A particular four-digit number N is such that: (a) The sum of N and 74 is a square; and (b) The difference between N and 15 is also a square. What is the number N? Step 1: Represent algebraically: N + 74 = q2 ? N 15 = r2 Step 2: Combine equations in some useful way. Perhaps if I subtract the second from the first, then Ill get rid of N, and have ? squares on the the difference of two RHS! 89 = (q + r)(q r) Step 3: Reason about factors Conveniently 89 is prime, and since q+r is

greater than q-r, then q + r = 89 and q r = 1. Solving these simultaneous equations ? gives us q = 45 and r = 44. Using one of the original equations: N = q2 74 = 452 74 = 1951. Source: Hamilton Paper Forming a Diophantine Equation Aim to factorise your equation. Question: Find all positive values of n for which is a (perfect) square. Hint: Perhaps complete the square? Solution: n = 35. n2 + 20n + 11 = k2 for some integer k. (n + 10)2 100 + 11 = k2 (n + 10)2 k2 = 89 (n + 10 k)(n + 10 + k) = 89

89 is prime. And since n + 10 + k > n + 10 k, n + 10 + k = 89 and n + 10 k = 1.? Using the latter, k = n + 9 So substituting into the first, n + 10 + n + 9 = 89. 2n = 70, so n = 35. For problems involving a square number, the difference of two squares is a handy factorisation tool! BMO Round 2 Round 1 Forming a Diophantine Equation Theres a variety of different strategies to factorise a Diophantine Equation. Question: Find all positive integers such that and are perfect squares. Based on the strategy on the previous question, we might have tried one equation subtracting the other to get the difference of two squares: But this is a bad strategy, because unlike before, we havent eliminated the variable on the LHS, and thus the above equation isnt particularly useful.

How could we deal with just 2 variables? Make the subject of each to get: ? ( 5+2)( 52 ) BMO Round 2 Round 1 Manipulating a Diophantine Equation Aim to factorise your equation. Question: Show that the following equation has no integer solutions: 1 1 5 + =

11 (Source: Maclaurin) Questions of this form are quite common, particularly in the Senior Maths Challenge/Olympiad. And the approach is always quite similar... Step 1: Its usually a good strategy in algebra to get rid of fractions: so multiply through by the dominators. ? = 5xy 11x + 11y Manipulating a Diophantine Equation Aim to factorise your equation. 11 +11 =5 Step 2: Try to get the equation in the form This is a bit on the fiddly side but becomes easier with practice. Note that Similarly So initially put the equation in the form Looking at the form above, it would seem to help to multiply by the

coefficient of (i.e. 5), giving This allows us to factorise as (5x 11)(5y 11) 121 = 0. The -121 is because we want to cancel out the +121 the results from the expansion of (5x 11)(5y 11). So Manipulating a Diophantine Equation Aim to factorise your equation. (5x 11)(5y 11) = 121 Step 3: Now consider possible factor pairs of the RHS as before. Since the RHS is 121 = 112, then the left hand brackets must be 1 121 or 11 11 or 121 1 or -1 -121, etc. (dont forget the negative values!) If 5x 11 = 1, then x is not an integer. If 5x 11 = 11, then x is not an integer. If 5x 11 = -1, then x = 2, but 5y 11 = -121, where y is not an integer. (And for the remaining three cases, there is no pair of positive integer solutions for x and y.)

Manipulating a Diophantine Equation Lets practice! Put in the form (ax b)(ay c) = d Use the 4 from 4xy -5 and -7 swap positions. (-5) x (-7) 7 + 5 = 4 x y 1 + 1 = 1 x y 4xy 5x 7y = 0 (4x 7)(4y 5) = 35

xy x ?y = 0 (x 1)(y 1) ?=1 3 + 3 = 2 x y 2xy 3x? 3y = 0 (2x 3)(2y ? 3) = 9 3xy 38x? 19y = 0 (3x - 19)(3y? 38) = 722 (Source: SMC) 1 + 2 = 3 x y 19

In general, this technique is helpful whenever we have a mixture of variables both individually and as their product, e.g. x, y and xy, and we wish to factorise to aid us in some way.. Now for each of these, try to find integer solutions for x and y! (if any) Dealing with divisions Suppose you are determining possible values of a variable in a division, aim to get the variable in the denominator only. Example: How many positive integer solutions for given that the following is also an integer: 100 We can rewrite this as: 100 ( 100 ) 100

= 1 100 100 ? (Alternatively, you could have used algebraic long division, or made the substitution k = 100-n) Now is just in the denominator. We can see that whenever 100 n divides 100, the fraction yields an integer. This gives 99, 98, 96, 95, 89, 79, 75, 50 Dealing with divisions In a division, sometimes we can analyse how we can modify the dividend so that it becomes divisible by the divisor. What is the sum of the values of n for which both n and are integers?

A: -8 B: -4 D: 4 E: 8 C: 0 Note that n 1 is divisible by n 1. Thus: (n 9)/(n-1) = (n2-1)/(n-1) 8/(n-1). So n-1 must divide 8. 2 2 SMC Level 5 Level 4

The possible values of n 1 are 8, 4, 2, 1, 1, 2, 4, 8, so n is 7, 3, 1, 0, 2, 3, 5, 9. The sum of these values is 8. (Note that the sum of the 8 values of n 1 is clearly 0, so the sum of the 8 values of n is 8.) Level 3 Level 2 Level 1 Dealing with surd expressions For Diophantine Equations involving surds, remember that the contents of the surd must be a square number. Square each side of the equation. Question: How many pairs of positive integers satisfy the equation: . A: 0 B: 1 D: 17

E: C: 2 SMC Squaring both sides: If is an integer, then must be an integer. This will be the case when for any positive integer (except , because then would be 0). But theres infinitely many choices for , thus theres infinitely many solutions for . Level 5 Level 4 Level 3 Level 2 Level 1

Restricting integer solutions When you have to find all integer solutions to some equation, theres usually some way to round down your search. Question: Solve the equation 5a ab = 9b2, where a and b are positive integers. Answer: a = 12, b = 2,?and a = 144, b = 4. Hint: What do we know about the RHS of the equation? What do this then tell us about 5a and ab? 9b2 0, therefore ab 5a. And since a is positive, then dividing both sides by a gives us b 5. This means we only need to try b = 1, 2, 3, 4 and 5! If we sub in b = 1, we get 4a = 9, for which theres no integer solution. Continuing with possible b, we eventually find all our solutions. In general, look out for things that are squared, as we know their value must be at least 0 (nonnegative). IMO Maclaurin Hamilton Cayley

Diophantine Equation Summary 1 2 3 4 5 Try to get whatever equation you have as a product on each side, so that you can reason about the factors. e.g. (x+10)(x-5) = 100 You can occasionally use the difference of two squares to factorise. e.g: 103x + x + 1 = k2 103x + x = k2 1 1001x = (k+1)(k-1) To factorise, you might need to think backwards to determine what could expand to get the terms you have. e.g. If you have x, y and xy in your expression, then (x+1)(y+1) would expand to give all 3 of these. In some contexts you can complete the square. Once factorised, you need to consider possibilities for the factors on each

side. Dont forget negative factors. You can use number theory knowledge to round down what factors could be. e.g. If you have k2, then prime factors in k come in pairs. e.g. If you have two factors that are consecutive, they are coprime and thus share no factors. Topic 2 Number Theory Part 4: Modular Arithmetic What the devil is it? On a digital clock, were we to specify the hour as 27, what wed actually mean is 3 in the morning. These hours are the same in modulo 24 arithmetic, i.e. our numbers are limited to 0 to 23, after which they loop back round.

27 3 (mod 24) Wed say 27 is congruent to 3 modulo/e/surds.mod 24 What the devil is it? Numbers in modulo k arithmetic are all equivalent to numbers in the range 0 to , where they then repeat. 0, 1, 2, 3, 4, 5, 6, 7, ... 0, 1, 2, 0, 1, 2, 0, 1, ... (mod 3) This operator usually means equivalent, and in this context more specifically means congruent. We can use modulo arithmetic to represent the remainder (also known as the residue) when we divide by some number. What the devil is it? How would we represent ? ? 0 ( 3)

How would we represent is one less than a multiple of 5. 4 ( 5 ) ? Or we could even use . Well see why that might be useful later. Properties of Modular Arithmetic Addition works just as if it was a normal equality. If 4 1(mod 3) then 4 + 5 1 + 5 (mod 3) Multiplication also works. If 4 1(mod 3) then 8 2(mod 3) Exponentiation also works (this one well use a lot!). If 5 2(mod 3) then 5k 2k (mod 3) for any k

Quickfire Examples Given that Then ? Given that Then Given that Then ? ? Given that Then ? Properties of Modular Arithmetic Multiplication also works.

If , then e.g. If , then But is the converse always true? i.e. If , then is ? If not, can you think of a counterexample? No. For example, note that , but when we divide each number by 4. However, it IS true when the number were dividing by is coprime to the modulo, i.e. . ? e.g. . i.e. . But 5 and 7 are coprime, so Properties of Modular Arithmetic Another common misconception (according to a BMO veteran) is that if: ) and then: This is not in general true!

Ill leave it as an exercise to find a counterexample Using Laws of Modular Arithmetic Often, it helps to consider all the possible residues. Question: Show that the arithmetic sequence 2, 5, 8, 11, ... does not contain a square number. Lets use modulo-3 arithmetic: The given sequence: 2, 5, 8, 11, ... 2, 2, 2, 2, ... (mod 3) The natural numbers: 0, 1, 2, 3, 4, 5, ... 0, 1, 2, 0, 1, 2, ... (mod 3) Then by the laws of modulo arithmetic: ? 02, 12, 22, 32, 42, 52, ... 02, 12, 22, 02, 12, 22, ... (mod 3) 0, 1, 1, 0, 1, 1, ... (mod 3) We can see therefore that the square numbers only give a remainder of 0 or 1 when divided by 3, so we never see any of the numbers on the sequence. Using laws of Modular Arithmetic Question: A square number is divided by 6. Which of the following could not be the remainder?

A: 0 B: 1 D: 3 E: 4 C: 2 When divided by 6, a whole number leaves remainder 0, 1, 2, 3, 4 or 5. So the possible remainders when a square number is divided by 6 are the remainders when 0, 1, 4, 9, 16 and 25 are divided by 6. These are 0, 1, 4, 3, 4 and 1 respectively, so a square number cannot leave remainder 2 (or remainder 5) when divided by 6.. SMC Level 5 Level 4 Level 3

Level 2 Level 1 Using laws of Modular Arithmetic Problem Revisited! Which of the following is divisible by 3 for every whole number x? (Now answer using modular arithmetic) A: x3- x B: x3 -1 3 D: x +1 E: x3 +x C: x3

SMC If for the natural numbers. x = 0, 1, 2 (mod 3) then: x3 0, 1, 8 0, 1, 2 (mod 3) Then x3 x 0-0, 1-1, 2-2 0, 0, 0 (mod 3) i.e. For all numbers of x, x3 x gives us a remainder of 0 when dividing by 3. Level 5 Level 4 Level 3 Level 2 Level 1 Using laws of Modular Arithmetic Source: Frosty Special 22 22

A square chessboard of sides 2n (for any n) is tiled with L-shapes, each of 3 squares, such that tiles dont overlap. Show that you will always have 1 square on the chessboard left untiled. Solution: Were finding the remainder when we divide (2n)2 = 22n = 4n by 3.? 4 = 1 (mod 3). So 4n = 1n = 1 (mod 3). Using laws of Modular Arithmetic Question: Show that for every positive integer n, 121n 25n + 1900n (-4)n is divisible by 2000. Hint: 2000 = 24 x 53, thus the only two coprime factors are 16 and 125. Solution: If 121 9 (mod 16), then 121n 9n (mod 16). Similarly 25 9 (mod 16) means that 25n 9n (mod 16).

Conveniently, since the second is subtracted, were left with 0 (mod 16) so far. 1900n 12n (mod 16) and (-4)n 12n (mod 16), where with the latter weve just added 16 to make the ? so overall we have 0 remainder positive. These again cancel, (mod 16), meaning that the expression is divisible by 16. Can use the same principle to show its divisible by 125. BMO Round 2 Round 1 Useful properties of square numbers Weve so far seen that it can sometimes be useful to consider the possible residues of a square number to eliminate possibilities (as well see for an upcoming example). Theres other handy properties to add to our toolkit: Prove that if that if a square number is even, then its divisible by 4. Prove that if a square number is odd, then

its one more than a multiple of 8. Answer: Answer: (Method 1) All powers in the prime factorisation of a square number are even, so if a factor of 2 appears (which it does because the square is even), it must appear at least twice, so the square is divisible by 4. Note first that if a square n2 is odd, then n is odd since odd odd = odd. ? (Method 2) If n2 is even, then n must be even since even even = even. Let n = 2k. Then n2 = (2k)2 = 4k2, which is clearly divisible by 4.

(Method 1) We need to show one less than a square is divisible by 8. n2 1 = (n-1)(n+1). Both n-1 and n+1 are even. But one must be divisible by 4. So we get a factor of 4 from one and 2 from the other, thus it is divisible by 8. ? (Method 2) If n is odd then let n = 2k+1. (2k+1)2 = 4k2 + 4k + 1 = 4k(k+1) + 1. One of k and k+1 is even, so 4k(k+1) is divisible by 8. Another problem revisited Question: If 3n2 = k(k+1), then what can we say about k and k+1? (Recall: k and k+1 are coprime) We previously established that either k is a square and k+1 is three times a square, or vice versa. We can eliminate one of these cases using modular arithmetic.

Case 1: k = a2 and k + 1 = 3b2 If k + 1 is a multiple of 3, then k has a residue of 2 modulo 3. But, we earlier saw square numbers can only have residues of 0?or 1 modulo 3. This contradicts that k is a square. Weve eliminated this as a case. Key Point: Modular Arithmetic can be useful to reason about what numbers can and cant be. Multiples and Residues Suppose were working in modulo 7 arithmetic, and that we start with a number 3, and find successive multiples: 3, 6, 9, 12, 15, 18, 21 3, 6, 2, 5, 1, 4, 0 (mod 7) Notice that we get all possible remainders/residues. Under what conditions do you think this happens? When the modulo (in this case 7) and the difference

? (in this case 3) are coprime. We say we have a complete residue system if we have all residues. We can see that because the last residue is 0, this number will be divisible by 7. i.e. Every 7th number will be divisible by 7 under the above conditions. Multiples and Residues Question: Determine the least possible value of the largest term in an arithmetic progression of seven distinct primes. Hint: If a is the first value and d is the difference, what properties must d have to avoid being divisible by something? Solution: 907 If our first number is prime, its clear that if the difference WASNT a multiple of 2, then every other number would be even. In terms of the theory on the last slide, we know we will see all possible residues (i.e. 0 and 1) in modulo-2 arithmetic if the number were finding multiples of, i.e. d, is not divisible by 2. Those with residues 0 will be divisible by 2 (unless it is 2 itself) and thus not prime. The same applies with 3 and 5 (the next two primes) so d must be divisible by these to avoid residues of 0 every 3 and 5 numbers respectively. 7 however is more interesting. In modulo-7 arithmetic, the first number a could be 7 while divisible by 7, its clearly prime. This means that a neednt be a multiple of 7 since its

possible we wont see a residue of 0 again until 7 numbers later in BMO the list (i.e. beyond the end of our list!). So lets make a = 7, and d a multiple of 2 x 3 x 5 = 30. After trying a Round 2 few multiples of 30, well find that d = 150. So the last number is Round 1 a + (n-1)d = 7 + (6x150) = 907 ? Multiples and Residues A bit of extra context for this problem: In the introduction, we saw Dirichlets Prime Number Theorem: All arithmetic sequences, where the initial term and the common difference are coprime, contain an infinite number of prime numbers. 3, 7, 11, 15, 19, ... 14, 16, 18, 20, 22, ... 3 and 4 are coprime, so sequence

will contain infinitely many prime numbers. But 14 and 2 are not coprime. As recently as 2004, it was proven that the sequence of prime numbers contains an arbitrarily long arithmetic progression. i.e. We can find an arithmetic sequence of any length. (This is now known as the Green-Tao Theorem) e.g. 3, 5, 7 and 47, 53, 59 are prime arithmetic sequences of length 3. The theorem however only proves their existence; it doesnt provide a method to find a sequence of a given length. The longest sequence found so far is of length 26. Dealing with remainders If x divided by y gives a remainder of z, then x z is divisible by y. For example, consider that 53 divided by 10 gives a remainder of 3. Then obviously 53 3 = 50 is divisible by 10. Question: When 144 is divided by the positive integer n, the remainder is 11. When 220 is divided by the positive integer n, the remainder is also 11. What is the value of n? A: 11

B: 15 D: 19 E: 38 C: 17 By our above rule, n divides 144 11 = 133 and 220 11 = 209. 133 = 19 x 7 and 209 = 19 x 11 So both are divisible by 19. Int Kangaroo Pink Grey Negative remainders Sometimes it can be more convenient to put our remainder as a

negative number for purposes of manipulation. For example, if the remainder when we divide a number by 3 is 2, then we could also say this remainder is -1 because they are congruent. By laws of modular arithmetic, 2n (-1)n (mod 3). We can more easily see the remainder oscillates between -1 (i.e. 2) and 1 as n increases. ? n (mod 3) 2n + 3n (-1) 3 -2? (mod 5) 7 -3? (mod 10) Playing with different moduli An extremely useful method is to consider your equation in different moduli to see if we can discover anything about the variables. Question: Is 2n + 3n be ever a perfect square? [Source OEIS] Hint: See what you find modulo 3 and modulo 5. Properties of n discovered in modulo 3: 2n + 3n (-1)n . But all squares are 0 or 1 modulo 3, so n must be even or the remainder

will be 2. So let n = 2k. ? Using this information, we now we have 22k + 32k = 4k + 9k. Properties of n discovered in modulo 5: 4k + 9k (-1)k + (-1)k 2 Since our number has to be square, consider possible residues modulo-5: these are 0, 1 and 4. This doesnt include 2 or 3 (i.e. -2). ? We have therefore shown 2n + 3n can never be a perfect square. Playing with different moduli Show that has no integer solutions. (Hint: try using mod 4) Since , we have . Similarly . So then considering all possibilities, ? However, . Thus there can be no integer solutions. Putting everything together

The following was a particularly badly answered BMO problem. But we can systematically reason through each step using the tips weve seen no magic required! Question: Let be an integer. Show that, if is an integer, then it is a perfect square. 1 2 3 First note that the question says IF [..] is an integer, THEN it is a square. We need to start with the assumption, and reason towards the conclusion dont be tempted to prove the opposite. If is an integer, what can we assert about ? a) It is a perfect square, since the square root has to be an integer. ? b) It is odd. What equation could we therefore write that would model this?

? Putting everything together The following was a particularly badly answered BMO problem. But we can systematically reason through each step using the tips weve seen no magic required! Question: Let be an integer. Show that, if is an integer, then it is a perfect square. 4 To reason about factors, we know its generally a good idea to put an equation in the form where we have the product of expressions on each side. So rearrange ? 5 Use this to reason about the factors (Hint: Weve seen this example before!)

and are coprime. We earlier determined that one of and is the square, and the other 3 times a square. ? We also earlier determined that if was a multiple of 3, then by modular arithmetic, couldnt be a square. Therefore is a square, and is three times a square. Putting everything together The following was a particularly badly answered BMO problem. But we can systematically reason through each step using the tips weve seen no magic required! Question: Let be an integer. Show that, if is an integer, then it is a perfect square. 6 When weve used an expression to represent a restriction on a number, we ought to substitute it into the original expression. Use ? 7

We earlier found that is a perfect square so what can we conclude? A square times a square is a square, since , so is a perfect square. ? Fermats Little Theorem Not to be confused with Fermats Last Theorem! If is prime, and is any integer (such that is not a multiple of ), then: 1 1 ( ) EXAMPLES: Fermats Little Theorem is a special case of Eulers Theorem, which makes use of something called Eulers Totient Function. Its not difficult, and worth looking up.

Fermats Little Theorem Show that . Were trying to show that: i.e. By Fermats Little Theorem: So: ? Modular Arithmetic Summary 1 When working in modulo-k arithmetic, all integers that give the same remainder when divided by k are equivalent/congruent. 2 In many problems, its useful to consider the possible residues of square numbers and cube numbers, for example to contradict the

other side of an equation. 3 If x divided by y gives a remainder of z, then x z is divisible by y. Use this in problems which specify the remainders for certain divisions. 4 Experimenting with different modulo can reveal information about your variables, particular for problems involving squared/cubed numbers. 5 If working in modulo-p arithmetic where p is prime, then we see all the possible residues for each p numbers in an arithmetic sequence, unless the common difference is a multiple of p. Topic 2 Number Theory

Part 5: Digit Problems Reasoning about last digits When we want to find the last digit of some expression, we can do our arithmetic modulo: ? 10 Using Laws of Modular Arithmetic Prove that the last digit of a square number can never be 2. If a square number DID end with a 2, then expressing this in modular arithmetic: Since , then . ? So square numbers cannot end in 2 or 3 or 7 or 8. Reasoning about last digits

3 1000 31 32 33 34 31000 3 9 7 1

1 27 7 (mod 10), i.e. we only ever need to keep the last digit when were working modulo-10 arithmetic. (mod 10) This is a very useful trick! If a 1 (mod n), then ak 1k 1 (mod n) So if 34 1 (mod 10), then (34)250 31000 1 (mod 10). A strategy to find the last digit in general of ab therefore is to try and get to 1 by incrementally raising the power, at which point we can multiply the power by anything we like! Reasoning about last digits Question: The value of 12004 + 32004 + 52004 + 72004 + 92004 is

calculated using a powerful computer. What is the units digit of the correct answer? A: 9 B: 7 D: 3 E: 1 C: 5 SMC The last digit of 34 is 1, as is the last digit of 74 and the last digit of 92. So the last digit of (34)501, that is of 32004, is 1. Similarly, the last digit of (74)501, that is of 72004, is 1 and the last digit of (92)1002, that is of 92004, is 1. Furthermore, 12004 = 1 and the last digit of 52004 is 5. So the units digit of the expression is 1 + 1 + 5 + 1 + 1, that is 9.

Level 5 Level 4 Level 3 Level 2 Level 1 Reasoning about last digits Question: Find the last non-zero digit of 50! Source: Team SMC We could use find the complete prime factorisation of 50!. 50! = 247 x 322 x 512 x 78 x 114 x 133 x 172 x 192 x 232 x 29 x 31 x 37 x 41 x 43 x 47. To find the number of twos for example, we look for multiples of 2 up to 50 (theres 25), then get bonus 2s from multiples of 4 (theres 12), then bonus 2s from multiples of 8 (6) then 16 (3) and the extra 2 from the 32, giving 47 in total. We eliminate the 5s to get rid of the zeros ? on the end of 50!, and thus must get rid of 12 twos as well, leaving 35 twos.

At this point, we can use modulo-10 arithmetic to find the last digit quickly, which we can do without a calculator because at any point we only ever need to keep the last digit: 235 x 322 x 78 x 114 x 133 x 172 x 192 x 232 x 29 x 31 x 37 x 41 x 43 x 47 8 x 9 x 1 x 1 x 7 x 9 x 1 x 9 x 9 x 1 x 7 x 1 x 3 x 7 2 (mod 10) Representing digit problems algebraically Suppose we have a 2-digit number ab. Q1: What range of values can each variable have? a: 1 to 9? b: 0 to 9? It couldnt be 0 otherwise wed have a 1-digit number. Q2: How could we represent the value (n) of the digit using a and b? e.g. If a = 7 and b = 2, we want n = 72

n = 10a?+ b Similarly, a 3-digit number abc could be represented as 100a + 10b + c Representing digit problems algebraically Question: An unfortunate number is a positive integer which is equal to 13 times the sum of its digits. Find all unfortunate numbers. Answer: 117, 156, ? 195 Lets try 2-digit numbers first. Algebraically: 10a + b = 13(a + b) So 3a + 12b = 0. But this gives us no solutions because one of a or b would have to be negative. Now try 3-digit numbers: 100a + 10b + c = 13(a + b + c) This simplifies to 29a = b + 4c Suppose a = 1. Then if b=1, c=7, giving 117 as a solution. We also get a=1, b=5, c=6 and a=1, b=9, c=5.

If a=2 or greater, then the LHS is at least 58. But b + 4c can never be big enough, because at most b=c=9, so b+4c = 45. Now try 4-digit numbers: We get 329a + 29b = c + 4d after simplification. But when a is at its lowest, i.e. a=1, and b=0, the c+4d can clearly never be big enough. Use what you know! I can represent the digits algebraically and form an equation. I know each of my digits can be between 1 and 9 (and 0 if not the first

digit) IMO Maclaurin Hamilton Cayley Topic 5 Number Theory Part 6: Rationality and Miscellaneous Irrationality of You may well have seen a proof before for the irrationality of 2. Recall that a rational number is one that can be expressed as a fraction. Aristotles Proof Use a proof by contradiction: Assume that 2 is rational. Then it can be expressed as a fraction in its simplest form , where and are coprime (if they werent

coprime, wed be able to simplify the fraction. Then squaring both sides: Then is even, and so is even. Therefore let . so Therefore is also even. Then and share a common factor of 2, contradicting that is in its simplest form. Something I just thought of... Lets reason about the factors on each side of the equation . We know that the powers in the prime factorisation of a square number need to be even. So for each of and , it can either not contain a 2, or its 2s come in pairs. Either way, we have an even number of 2s on the LHS of the equation, and an odd number on the RHS due to the extra 2.

Thus the equation has no integer solutions, i.e. a square number cannot be twice another square number. A rationality BMO problem Question: Let be a set of rational numbers with the following properties: 1) is an element of 2) If is an element of , then both is an element of and is an element of Prove that contains all rational numbers in the interval . What would the structure of our proof look like?: 1. Start with some rational number in the interval . 2. Show somehow that we can use either of the statements in (2) until we eventually get to a half (satisfying (1)), and thus we can always find some chain starting from to get to any rational number in the interval. ? Solution: We could show that if x is some rational number (for some coprime and , as with the irrationality of 2 proof), then and is But we get nicer expressions if we do it backwards: if , then . Similarly, if , then

This means we can subtract the numerator from the denominator, and reciprocate the fraction if its above 1, and still have a value in?the set . e.g. 5/7 5/2 2/5 2/3 2/1 1/2 (Continued on next slide) A rationality BMO problem Question: Let be a set of rational numbers with the following properties: 1) is an element of 2) If is an element of , then both is an element of and is an element of Prove that contains all rational numbers in the interval . e.g. 5/7 5/2 2/5 2/3 2/1 1/2 All that remains therefore is to prove that we can make sure a chain from any to eventually get to . Informally, we could argue that as the numerator or denominator can always decrease in each step, then one of them will reach 1. If the denominator reaches 1 first and we have , we know is in the set. If we have , then we can always use our rule to reduce by 1 each time until we reach . A more formal proof could use a proof by contradiction, found here: http://www.theproblemsite.com/problems/mathhs/2008/Jun_1_solution.asp BMO Round 2

Round 1 Topic 2 Number Theory Part 7: Epilogue The rest of these slides dont explore any theory that is likely to be use in any Maths Challenges/Olympiads or university interviews, but explore an interesting area of Number Theory... Lets finish with something light... Analytic Number Theory! = Mathematical analysis + Number Theory Using differentiation, integration, limits, and usually considering real and complex numbers. Properties of integers. Thats interesting: were using analysis, which concerns real and complex numbers,

to reason about the integers. Lets finish with something light... Analytic Number Theory! Theres broadly two types of problem studied in this field: Those involving multiplication + Those involving addition ...which includes reasoning about factors. Usually concerns properties of prime numbers. e.g. The yet unproven Goldbach Conjecture: every even integer is the sum of two primes. Lets have a tiny bit of a look at prime numbers... Distribution of primes Prime Number Theorem:

The probability that a randomly chosen large number N is prime is approximately 1 in ln(N) Since the graph of ln(N) always increases but gradually slows down, this suggests (as we might expect) that primes gradually become more spread out for larger numbers, but that the gap between prime numbers gradually levels off. P(10,000 is prime) = 1/ ln(10000) = 0.11 So around this number wed expect roughly 1 in 10 numbers to be prime. P(1 billion is prime) = 1/ ln(1,000,000,000) = 0.048 So around this number wed expect roughly 1 in 20 numbers to be prime. Counting primes (x) The prime-counting function, i.e. the number of primes up to and including x. So , because there are 4 prime numbers (2, 3, 5, 7) up to 10. (Note that the symbol is being used a function here, not as the constant you know and love!) Could we use the Prime Number Theorem to come up with an estimate for p(x)? Consider 100 people who have been asked to come to your party. If each person has a 0.3 chance of coming to your party, youd expect 100 x 0.3 = 30 people to come.

But more generally, if each person had different probabilities of coming to your birthday, you could add the probabilities to get an estimate for the total coming. Similarly, if we added up the probability of each number of prime up to x, wed get an estimate of the number of primes up to x. So: Counting primes But since ln(x) is a continuous function, we may as well use integration instead, finding the area under the graph: The function on the RHS is known as the logarithmic integral, written Li(x) But if we consider the graph of ln(x), and note that as x becomes large, the gradient of ln(x) becomes 0, and thus we could come up with a looser but easier to calculate approximation that assumes we use the same probability ln(x) for all numbers up to x (rather than calculate ln(k) for each k up to x as before). Then, given the probability is constant, then going back to our party analogy, we can just multiply this constant probability by the number of people to get the estimate attendance, i.e. Multiply 1/ln(x) by x to get an estimate number of primes: Counting primes The graph indicates how accurate these two estimates area compared to the true number of primes (x).

1.1 means weve overestimated by 10% We can see that this estimate is 99% accurate once we consider the number of primes up to about 100,000 The th prime? Theres currently no formula to generate the th prime. But we can use the approximation seen earlier. If there are prime numbers up to , this suggests that the () th prime number is roughly . That means that the th prime number will be roughly Example: The actual 100,000th prime number is just under 1.3 million And 1.15 million. This percentage error is reduced as the number becomes larger.

The probability two numbers are coprime? To solve this problem, lets first consider the Riemann Zeta Function (which these resources are named after!) So for example: Which curiously comes to (and yes, here means 3.14) Euler proved that such as sum is related to a product involving primes: For example: The probability two numbers are coprime? How then is this related to the probability of two numbers being coprime? Whats the probability an integer is divisible by 4? 1 ? 4

Whats the probability that two numbers are divisible by some number p? 1 p?2 Whats the probability that neither of two numbers is divisible by a number p? 1 - ?12 p To consider whether two numbers are coprime, we need to test whether each possible prime p is a factor of both. We need not test whether theyre both divisible by non-primes, because if for example both numbers are divisible by 8, we would have already earlier found that they are divisible by 2. It also ensures we have independence: the probability of a number being divisible by 2 is not affected by the probability of being divisible by 3, but if a number is divisible by 2 say, then this increases the chance its divisible by 4 (from 0.25 to 0.5). The probability two numbers are coprime?

Then by considering all possible primes p, the probability is: The RHS looks familiar! We saw that the product of such expressions involving primes was the same as the Riemann Zeta Function. So the probability is (2)-1, which is (2/6)-1 6 2 I find this remarkable, that , usually associated with circles, would arise in a probability involving coprimality!

Recently Viewed Presentations