Prime number between 7902 and 7918

Question

Which number between the interval 7902 & 7918 can be divided without remainder only to itself and to the number 1?

Answer 1

You want to find a prime between 7902 and 7918. One way to do this is to use a number sieve, or since there are only a few small numbers, brute force by testing divisors between 1 and 88 ($\lfloor \sqrt{7918}\rfloor$). From this we see 7907 is prime.

Answer 2

The requirement is that the number is prime, so this excludes the even numbers, leaving $$ 7903;7905;7907;7909;7911;7913;7915;7917. $$ We can remove $7905$ and $7915$ because they're divisible by $5$; $7911$ and $7917$ are divisible by $3$. Moreover $7903$ is divisible by $7$ and $7909$ is divisible by $11$; note that the next odd multiples of $7$ and $11$ are larger than $7917$. So we're left with $$ 7907; 7913. $$ At this point there's nothing else to do than divisions. Since we have already tried $2$, $3$, $5$, $7$ and $11$, the list of primes to check is $$ 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83. $$ The next one is $89$, but since $89^2=7921>7913$, if a prime bigger than $83$ divides one of the numbers, also one not larger than $83$ would.

You can save some work by noticing that when you divide $7907$ by $13$ is $3$, so $7913=7907+6$ isn't divisible by $13$ either. Similarly, $7907\bmod 17=2$ (this denotes the remainder), so $7913$ isn't divisible by $17$ either. Go on until you find a prime divisor for one of the numbers and continue with the other alone.

Note that there's no guarantee that in a given interval of numbers you'll find a prime.

This is what Pari-GP says:

? isprime(7907)
%1 = 1
? isprime(7913)
%2 = 0
? factor(7913)
%3 = 
[ 41 1]

[193 1]