- #1

- 734

- 186

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