Question

I DARE you find the prime in these set of numbers: 961, 1961, 2961, 3961, 4961, 5961, 6961, 7961, 8961, 9961. I'll give you a medal and follow you if you find the prime. Hint: What's 31^2?

Answer 1

6961

Answer 2

Pfft

Answer 3

6961 is a prime number

Answer 4

@OS31P.vnd I DARE you to find the next prime ending with 961 :-)

Answer 5

*

Answer 6

^ agreed

Answer 7

http://primes.utm.edu/lists/small/10000.txt

Answer 8

19961

Answer 9

ok i dare u to find 10 prime numbers all its digits 1

Answer 10

for example 11 is prime all its digits 1 :D

Answer 11

the dumb way i can think of is to test for divisibility of all primes less than \(\large \sqrt{n}\)
I'm not sure how to use the given hint :/

Answer 12

@KingGeorge

Answer 13

@oldrin.bataku

Answer 14

I couldn't resist. We know that \(31^2=961\). So 961 is clearly not prime. Furthermore, since the sum of digits is divisible by 3, we know that 2961, 5961, and 8961 aren't prime. Using a similar divisibility test, 9961 is divisible by 7, so that isn't prime either. These are the easy ones.

We're left with \[1961,3961,4961,6961,8961\]

Answer 15

A test for 11 tells us that \(4961\) is divisible by 11.

Answer 16

So we only have\(1961,3961,6961\) and \(7961\) left.

Answer 17

Ahhh looks this problem is designed specifically for this approach ! xD

Answer 18

That method won't work well with 1961. I can't actually find a suitable primality test easy enough to do by hand other than guess and check for the remaining numbers (1961 would take the longest).

Answer 19

I suppose we could use fast exponentiation with 2 (the hardest part will be reducing modulo \(n\)) to see that\[1961,3961,7961\]are all composite since they fail Fermat's little theorem...

Answer 20

For example, write \[1960=2^{10}+2^9+2^8+2^7+2^5+2^3\]Then\[\large\begin{aligned}2^{1960}&\equiv2^{2^{10}+2^9+2^8+2^7+2^5+2^3}\pmod{1961}\\
&\equiv2^{2^{10}}2^{2^9}2^{2^8}2^{2^7}2^{2^5}2^{2^3}\pmod{1961}\\
\end{aligned}\]
Then we have that \(2^{2^3}\equiv256\pmod{1961}\), \[2^{2^4}\equiv256^2\equiv823\pmod{1961}\]\[2^{2^5}\equiv823^2\equiv784\pmod{1961}\]\[2^{2^6}\equiv784^2\equiv863\pmod{1961}\]\[2^{2^7}\equiv863^2\equiv-411\pmod{1961}\]\[2^{2^8}\equiv(-411)^2\equiv275\pmod{1961}\]\[2^{2^9}\equiv275^2\equiv1107\pmod{1961}\]\[2^{2^{10}}\equiv1107^2\equiv1785\pmod{1961}\]These are not trivial steps to do by hand, and it probably would be easier to just guess and check. But the we see that\[2^{1960}\equiv-1785*1107*275*411*784*256\equiv1785\not\equiv\pm1\pmod{1961}\]So 1961 doesn't satisfy Fermat's little theorem and must therefore be composite.

Answer 21

It would also have been possible to just exponentiate to 980 and get a similar contradiction. Or perhaps something a bit easier would be the Miller-Rabin test.

Answer 22

You could do similar things for 3961 and 7961, or you could notice that they're divisible by 17 and 19 respectively and therefore not prime. Leaving only 6961.

Answer 23

Or we use the divisibility rules from here. http://en.wikipedia.org/wiki/Divisibility_rule

Then 3961 is divisible 17 since 396-5=391 is divisible by 17 since 39-5=34=17*2 is divisible by 17.

Also 7961 is divisible by 19 since 796+2=798 is divisible by 19 since 79+16=95 is divisible by 19 since 9+10=19 is divisible by 19.

Finally, 1961 is divisible by 37 since 196-11=185=37*5 is divisible by 37.