- #1
Math100
- 768
- 219
- Homework Statement
- Determine whether the integer ## 701 ## is prime by testing all primes ## p\leq\sqrt{701} ## as possible divisors. Do the same for the integer ## 1009 ##.
- Relevant Equations
- None.
Proof:
Consider all primes ## p\leq\sqrt{701}\leq 27 ##.
Note that ## 701=2(350)+1 ##
## =3(233)+2 ##
## =5(140)+1 ##
## =7(100)+1 ##
## =11(63)+8 ##
## =13(53)+12 ##
## =17(41)+4 ##
## =19(36)+17 ##
## =23(30)+11 ##.
Thus, no prime numbers less than ## 27 ## are divisible by the integer ## 701 ##.
Therefore, the integer ## 701 ## is prime.
Now, we consider all primes ## p\leq\sqrt{1009}\leq 32 ##.
Note that ## 1009=2(504)+1 ##
## =3(336)+1 ##
## =5(201)+4 ##
## =7(144)+1 ##
## =11(91)+8 ##
## =13(77)+8 ##
## =17(59)+6 ##
## =19(53)+2 ##
## =23(43)+20 ##
## =29(34)+23 ##
## =31(32)+17 ##.
Thus, no prime numbers less than ## 32 ## are divisible by the integer ## 1009 ##.
Therefore, the integer ## 1009 ## is prime.
Consider all primes ## p\leq\sqrt{701}\leq 27 ##.
Note that ## 701=2(350)+1 ##
## =3(233)+2 ##
## =5(140)+1 ##
## =7(100)+1 ##
## =11(63)+8 ##
## =13(53)+12 ##
## =17(41)+4 ##
## =19(36)+17 ##
## =23(30)+11 ##.
Thus, no prime numbers less than ## 27 ## are divisible by the integer ## 701 ##.
Therefore, the integer ## 701 ## is prime.
Now, we consider all primes ## p\leq\sqrt{1009}\leq 32 ##.
Note that ## 1009=2(504)+1 ##
## =3(336)+1 ##
## =5(201)+4 ##
## =7(144)+1 ##
## =11(91)+8 ##
## =13(77)+8 ##
## =17(59)+6 ##
## =19(53)+2 ##
## =23(43)+20 ##
## =29(34)+23 ##
## =31(32)+17 ##.
Thus, no prime numbers less than ## 32 ## are divisible by the integer ## 1009 ##.
Therefore, the integer ## 1009 ## is prime.