How to determine whether 761 is a prime number?

Question

A prime number is a number that has only two factors, 1 and itself.

How to effectively determine 761 is a prime number? In other word, How to proof number 761 can not be divided by any number from 2 - 760. You need to try and figure out whether 761 can be divided by those numbers.

Hint: Remember rules of division, for example,

A number ended in 0,2,4,6,8 can be divided by 2.

A number can be divided by 3 shall have the sum of all digits divisible by 3.

A number can be divided by 4 shall have the last two digits divisible by 4.

A number can be divided by 5 shall end with 0 or 5.

A number can be divided by 6 shall be divisible by 2 and 3.

A number can be divided by 8 shall be divisible by 2 and 4.

A number can be divided by 9 shall have the sum of all digits divisible by 9.

A number can be divided by 10 shall have its last digit 0.

Last but not least, try to use square root of a number to cut the trial process in half. In this case, the closest number to √761 ≅ 27, so you only need to try from 2 to 27.

Answer 1

We've been given a lot of helpful hints which can cut the time down a lot!

First, take the number 761 and see if it is divisible by 2. It isn't, so we know it also cannot be divisible by multiples of 2. We do the same with 3. The sum of the digits is not divisible by 3, so 761 is not divisible by 3. It also cannot be divisible by multiples of 3. Let's also check if it's divisible by 5. It does not end in a 0 or 5, so it cannot be divisible by 5, nor can it be divisible by multiples of 5. We also know with the given hint that we only need to look at numbers up to 27. This makes the remaining numbers it can be divisible by 7, 11, 13, 17, 19, and 23, because none of those are multiples of 2, 3, and 5. These are also all prime numbers.

From here, it is a trial process of dividing those remaining numbers into 761. We've already narrowed it down to 6 numbers, so our trial time will be very short. When we divide 7 into 761, we get 108.71, which is not a whole number. So 761 is not divisible by 7. We do the same for the remaining numbers (11, 13, 17, 19, and 23), and none of them give us a whole number.

Therefore, we can know that 761 is a prime number, divisible only by 1 and itself.