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