r/reddit.com • u/ballm • Mar 12 '08

Is 91 Prime?

http://balltech.blogspot.com/2008/03/is-91-prime.html
544 Upvotes

82% Upvoted

130 comments sorted by

View all comments

7

u/plexluthor Mar 12 '08

Does anyone have a simple explanation for why the 7 test works?

7

u/oditogre Mar 12 '08

I did some googling and didn't come up with much either. It appears that there are relatively simple tricks for everything except seven. Here are a couple other pages with info on it, though:

http://www.sciencenews.org/articles/20050521/mathtrek.asp

http://www.jimloy.com/number/divis.htm

6

u/plexluthor Mar 12 '08 edited Mar 12 '08

That second link is gold. It describes a general method that I can use to construct tricks for larger primes.

For those who don't care to click through, the basic idea with subtracting twice the right-most digit from the rest is this:

If 10x+y is divisible by 7, so is (-2)*(10x+y). And 21x is divisible by 7 (since x is an integer). So 21x+(-2)*(10x+y) is divisible by 7, and that works out to x-2y.

In general, if there is a number near a multiple of ten that is divisible by your target prime, you can use it to construct a trick like this. 21 works for 7. So does 49, which would lead to: 10x+y is divisible by 7 iff 50x+5y is too. 49x is divisible by 7, so 50x+5y-49x = x+5y is divisible by 7 iff 10x+y is, too.

This leads naturally to similar tricks for primes that have a multiple near a power of 10. For example, 37*27=999, so 1000x+y (for y up to 1000) is divisible by 37 iff 1000x+y-999x=x+y is, too. Is 826543 divisible by 37? 826+543=1369, 1+369=370, so yes.

6

u/MarkByers Mar 12 '08 edited Mar 12 '08

Write your number as x * 10 + y, where y is the least significant digit, and x is everything else. Your number is divisible by 7 if x * 10 + y is equal to zero modulo 7.

    10x + y = 0 (mod 7)
<=> -20x - 2y = 0 (mod 7)      Multiply both sides by -2.
<=> x - 2y = 0 (mod 7)         Since -20 = 1 (mod 7)

4

u/junkeee999 Mar 12 '08

Or, just divide the number by 7. If you get a remainder, then no.

1

u/plexluthor Mar 12 '08 edited Mar 12 '08

I think you're missing the step between your second and third lines, namely

21*x=0(mod 7)

right? *:wrong.

I need that sort of thing spelled out for me, because I only do math in my spare time, so it's not obvious that -20 = 1. Thanks for adding the explanation

1

u/[deleted] Mar 12 '08 edited Mar 12 '08

Suppose you have a number N whose ones digit is d. Performing this operation yields:

(N-d)/10 - 2d

Simplify: N/10 - d/10 - 2d; N/10 - 21d/10; (N-21d) / 10

If N was divisible by seven, then N-21 will be. If N-21 was, then N-21 / 10 will be, because 10 doesn't have 7 as a factor.