Number Theory Flashcards
Define: prime number
A prime number is a positive integer with exactly two positive integer divisors: 1 and itself.
Why is 1 not a prime number?
No, 1 only has one positive integer divisor, namely 1. Prime numbers must have exactly two (different!) positive integer divisors.
Fundamental Theorem of Arithmetic,
The fact that every positive integer greater than 1 can be decomposed into a product of primes in exactly one way is known as the Fundamental Theorem of Arithmetic.
How many different pairs of prime numbers have a sum of 43?
One of them must be even, and the other must be odd. One of them has to be 2 (the only even prime!), so 2 and 41 is the only possible pair.
How many prime numbers are less than 100?
There are 25 primes under 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97; But there are only 21 in the next 100.
Recite the primes less than 30.
2 3 5 7 11 13 17 19 23 29
List the primes between 30 to 72.
31 37 41 43 47 53 59 61 67 71
List the primes from 72 to 115.
73 79 83 89 97 101 103 107 109 113
List the primes from 115 to 175
127 131 137 139 149 151 157 163 167 173
List the primes from 175 to 230
179 181 191 193 197 199 211 223 227 229
List the primes from 230 to 1015. (Hard)
233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013
How many primes exist between 945 and 1013?
10. 947 953 967 971 977 983 991 997 1009 1013
What is the 2nd digit divisibility rule for 11?
If you sum every second digit and then subtract all other digits and the answer is divisible by 11
What is the shrinking number algorithm for testing divisibility by 7?
- Subtract the first digit from a number made by the other digits. 2. If that number is divisible by 11 then the original number is, too. 3. Repeat if needed Example: 14641 1. 1464 − 1 = 1463 2. 146 − 3 = 143 3. 14 − 3 = 11 4. 11 mod 11 = 0 so 14641 is divisible by 11
Three consecutive positive prime numbers have a sum that is a multiple of 7. What is the key to calculating the least possible sum?
- In such a case, you could start listing the first few examples and see where they get you.
- It helps to have those primes memorized.
- Guess-and-check is the best way to go.
- Dealing with the SUM of three primes is not so easy, because there is no formula that gives three consecutive primes.
Three consecutive positive prime numbers have a sum that is a multiple of 7. What is the least possible sum?
2+3+5 = 10 3+5+7 = 15 5+7+11 = 23 7+11+13 = 31 11+13+17 = 41 **13+17+19 = 49**
Guess-and-check is the best way to go. The key point is this: when a problem seems to offer no great entry point, start by trying some examples. This is the fastest way. Dealing with the SUM of three primes is not so easy, because there is no formula that gives three consecutive primes.
Which is easier: problems involving product of primes or sum of primes?
Dealing with the SUM of three primes is not so easy, because there is no formula that gives three consecutive primes. Working with the product of primes is much easier.
What is the algorithm for solving the following problem: what is the greatest three-digit prime number each of whose digits are also prime?
- Make a list of the single digit primes: 2, 3,5, 7.
- The first digit we should try has to be 7 because that will give us the largest number.
- The last digit cannot be 5 or 2.
- Cannot be 777 (obviously divisible by 7).
- Then we try the first candidate which is: 773.
- Need to check only up to square root of 773.
- The square root of 773 is << 30 - in fact it’s under 29 - we only need to check primes less than 29.
- Easy to see that 773 is not divisible by 2, 3, 5, and 7.
- For 11, 13, .. 23 we use the following algorithm:
- For 11, clearly 770 is divisible by 11 (770=11∗70), so the next multiple would be 770 + 11 = 781, bigger than our number.
- 13 goes evenly into 780 (60∗13), so 780-13 is also divisible by 13, but that’s 767, so we’re safe.
- Use the above algorithm using 17, 19 and 23 to show that 773 is prime.
Is 70022 divisible by 7?
70022 = 70000 + 22. 70000 mod 7 = 0 while 22 mod 7=1.
Splitting algorithm for determining if n mod m = 0?
- If a is divisible by k, and b is NOT divisible by k, then, n is NOT divisible by k.
- OR: If a and b are BOTH divisible by k, then so is n!
Is 26004 divisible by by 13?
Since 26004=26000+4=1000∗2∗13+4, so 26004 is NOT divisible by 13.
What is the trick to solving 201419 mod 19 = 0?
- We use the splitting strategy.
- We notice that 2014=2⋅19⋅53
- So: 201419=201400+19=100∗2∗19∗53+19.
How do we quickly tell if a number is divisible by 4?
The proper way to say it is that the last two digits form a number divisible by 4.
Is 12345678932 divisible by 4?
32 is divisible by 4 so 12345678932 is
Prove the divisibility rule for 4.
- Using the splitting strategy, any number n can be written as: n=a*100 + b
- a*100 is divisible by 4.
- So if b is divisible by 4, then n is also divisible by 4.
What is the proof for the divisibility rule for 3?
- Any number n can be split into its digits times their place values: Eg: a*1000 + b*100 + c*10 + d.
- They can be re-written as: a*(999 + 1) + b*(99+1) + c*(9 +) + d = (a*999 + b*99 + c*9) + (a+b+c+d)
- This can be re-written as: (a number which is a multiple of 9 )+a+b+c+d.
- A number which is a multiple of 9 is divisible by 3.
- By the splitting rule, it follows that n is divisible by 3.
Divisibility by 6?
Last digit must be even, and the digits must sum to a multiple of 3.
What is the least positive integer greater than 1 that is a factor of 11000+1100+11?
- 11⋅(1000+100+1) = 11⋅1101
- 1101 is divisible by 3 (sum of digits)
Another way:
- because the digits sum to 2+2+2 = 6.
- It’s OK to sum the digits of each number separately, and then sum those results.
- It works in this situation because there are no carries, but even if there are carries then the divisibility test still works this way, where you can sum the digits of each part before doing further computations.)
Trick to determining: Product of the first 25 prime numbers mod 4
Except for 2, all primes are odd.
Product of the first 25 prime numbers mod 4?
- There’s only one 2 among its divisors.
- When you divide 4 into an even number that’s not divisible by 4 the remainder is 2.
The four-digit number 374n is divisible by 18. Determine n.
- It must be even and 374n should be divisible by 9.
- 3+7+4 = 14.
- 14+4 = 18 which is divisible by 9.
- 4 is even.
- Therefore n=4.
If n is divisible by a and also by b, is it divisible by the product a⋅b?
False. Counter-example:
- Let a=4, b=6, and n=12
- 12 mod 24 = -12 ( 12 = 24*0 + (-12))
How many 3-digit palindromes are multiples of 3?
- Number has to be of form ABA where A is not zero.
- 2A + B mod 3 = 0
- The easiest way to finish the problem is to make a table.
- We list the values of A and then all the possible values of B that give a sum that is a multiple of 3.
- Total number of entries is 30.
A B 1 1 , 4 , 7 2 2 , 5 , 8 3 0 , 3 , 6 , 9 4 1 , 4 , 7 5 2 , 5 , 8 6 0 , 3 , 6 , 9 7 1 , 4 , 7 8 2 , 5 , 8 9 0 , 3 , 6 , 9
Tickets to a concert cost 16 dollars for adults and 13 dollars for children. A group of adults and children spent 154 dollars for its tickets. How many adults were in the group?
- Set up an Equation
- Equation: 16a +13c = 154
- Since we don’t have another equation, just guess and check
- The number of children must be even.
- Guess and check
