Number Theory

Question 1

Define: prime number

Answer 1

A prime number is a positive integer with exactly two positive integer divisors: 1 and itself.

Question 2

Why is 1 not a prime number?

Answer 2

No, 1 only has one positive integer divisor, namely 1. Prime numbers must have exactly two (different!) positive integer divisors.

Question 3

Fundamental Theorem of Arithmetic,

Answer 3

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.

Question 4

How many different pairs of prime numbers have a sum of 43?

Answer 4

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.

Question 5

How many prime numbers are less than 100?

Answer 5

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.

Question 6

Recite the primes less than 30.

Answer 6

2 3 5 7 11 13 17 19 23 29

Question 7

List the primes between 30 to 72.

Answer 7

31 37 41 43 47 53 59 61 67 71

Question 8

List the primes from 72 to 115.

Answer 8

73 79 83 89 97 101 103 107 109 113

Question 9

List the primes from 115 to 175

Answer 9

127 131 137 139 149 151 157 163 167 173

Question 10

List the primes from 175 to 230

Answer 10

179 181 191 193 197 199 211 223 227 229

Question 11

List the primes from 230 to 1015. (Hard)

Answer 11

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

Question 12

How many primes exist between 945 and 1013?

Answer 12

10. 947 953 967 971 977 983 991 997 1009 1013

Question 13

What is the 2nd digit divisibility rule for 11?

Answer 13

If you sum every second digit and then subtract all other digits and the answer is divisible by 11

Question 14

What is the shrinking number algorithm for testing divisibility by 7?

Answer 14

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

Question 15

Three consecutive positive prime numbers have a sum that is a multiple of 7. What is the key to calculating the least possible sum?

Answer 15

1. In such a case, you could start listing the first few examples and see where they get you.
2. It helps to have those primes memorized.
3. Guess-and-check is the best way to go.
4. Dealing with the SUM of three primes is not so easy, because there is no formula that gives three consecutive primes.

Question 16

Three consecutive positive prime numbers have a sum that is a multiple of 7. What is the least possible sum?

Answer 16

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.

Question 17

Which is easier: problems involving product of primes or sum of primes?

Answer 17

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.

Question 18

What is the algorithm for solving the following problem: what is the greatest three-digit prime number each of whose digits are also prime?

Answer 18

1. Make a list of the single digit primes: 2, 3,5, 7.
2. The first digit we should try has to be 7 because that will give us the largest number.
3. The last digit cannot be 5 or 2.
4. Cannot be 777 (obviously divisible by 7).
5. Then we try the first candidate which is: 773.
6. Need to check only up to square root of 773.
7. The square root of 773 is << 30 - in fact it’s under 29 - we only need to check primes less than 29.
8. Easy to see that 773 is not divisible by 2, 3, 5, and 7.
9. For 11, 13, .. 23 we use the following algorithm:
   
   1. For 11, clearly 770 is divisible by 11 (770=11∗70), so the next multiple would be 770 + 11 = 781, bigger than our number.
   2. 13 goes evenly into 780 (60∗13), so 780-13 is also divisible by 13, but that’s 767, so we’re safe.
   3. Use the above algorithm using 17, 19 and 23 to show that 773 is prime.

Question 19

Is 70022 divisible by 7?

Answer 19

70022 = 70000 + 22. 70000 mod 7 = 0 while 22 mod 7=1.

Question 20

Splitting algorithm for determining if n mod m = 0?

Answer 20

1. If a is divisible by k, and b is NOT divisible by k, then, n is NOT divisible by k.
2. OR: If a and b are BOTH divisible by k, then so is n!

Question 21

Is 26004 divisible by by 13?

Answer 21

Since 26004=26000+4=1000∗2∗13+4, so 26004 is NOT divisible by 13.

Question 22

What is the trick to solving 201419 mod 19 = 0?

Answer 22

1. We use the splitting strategy.
2. We notice that 2014=2⋅19⋅53
3. So: 201419=201400+19=100∗2∗19∗53+19.

Question 23

How do we quickly tell if a number is divisible by 4?

Answer 23

The proper way to say it is that the last two digits form a number divisible by 4.

Question 24

Is 12345678932 divisible by 4?

Answer 24

32 is divisible by 4 so 12345678932 is

Question 25

Prove the divisibility rule for 4.

Answer 25

1. Using the splitting strategy, any number n can be written as: n=a*100 + b
2. a*100 is divisible by 4.
3. So if b is divisible by 4, then n is also divisible by 4.

Question 26

What is the proof for the divisibility rule for 3?

Answer 26

1. Any number n can be split into its digits times their place values: Eg: a*1000 + b*100 + c*10 + d.
2. 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)
3. This can be re-written as: (a number which is a multiple of 9 )+a+b+c+d.
4. A number which is a multiple of 9 is divisible by 3.
5. By the splitting rule, it follows that n is divisible by 3.

Question 27

Divisibility by 6?

Answer 27

Last digit must be even, and the digits must sum to a multiple of 3.

Question 28

What is the least positive integer greater than 1 that is a factor of 11000+1100+11?

Answer 28

1. 11⋅(1000+100+1) = 11⋅1101
2. 1101 is divisible by 3 (sum of digits)

Another way:

1. because the digits sum to 2+2+2 = 6.
2. It’s OK to sum the digits of each number separately, and then sum those results.
3. 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.)

Question 29

Trick to determining: Product of the first 25 prime numbers mod 4

Answer 29

Except for 2, all primes are odd.

Question 30

Product of the first 25 prime numbers mod 4?

Answer 30

1. There’s only one 2 among its divisors.
2. When you divide 4 into an even number that’s not divisible by 4 the remainder is 2.

Question 31

The four-digit number 374n is divisible by 18. Determine n.

Answer 31

1. It must be even and 374n should be divisible by 9.
2. 3+7+4 = 14.
3. 14+4 = 18 which is divisible by 9.
4. 4 is even.
5. Therefore n=4.

Question 32

If n is divisible by a and also by b, is it divisible by the product a⋅b?

Answer 32

False. Counter-example:

1. Let a=4, b=6, and n=12
2. 12 mod 24 = -12 ( 12 = 24*0 + (-12))

Question 33

How many 3-digit palindromes are multiples of 3?

Answer 33

1. Number has to be of form ABA where A is not zero.
2. 2A + B mod 3 = 0
3. The easiest way to finish the problem is to make a table.
   
   1. We list the values of A and then all the possible values of B that give a sum that is a multiple of 3.
   2. 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

Question 34

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?

Answer 34

1. Set up an Equation
2. Equation: 16a +13c = 154
3. Since we don’t have another equation, just guess and check
4. The number of children must be even.
5. Guess and check