Right. And, indeed, when I need to check in my head whether a smallish number like 1033 is prime, most of what I do isn’t factoring. E.g.: 1033+17 = 1050 = 50.21, ruling out {2,3,5,7,17} in a single go but not identifying any factors or (even approximate) quotients. 1033-13 = 1020 = 20.51, ruling out {2,3,5,13,17} instead. Etc.
I also assumed that Eliezer’s intention was that you shouldn’t be doing this sort of thing.
[EDITED to fix formatting screwage—asterisks treated as markup rather than multiplication—my apologies for any mystification this caused.]
(Initial remark: damn, I see that what I wrote got screwed up by asterisks getting treated as markup characters; perhaps everything would have been clear without that. Will fix once I’ve finished writing this.)
I’m not sure it really warrants dignifying with the term “method”, but:
The relations I’m looking for are of the form n=a+b or n=a-b where a,b (1) are easy to factor because they’re products of small primes, and (2) have no common factor. In that case, you know that n isn’t a multiple of any of those prime numbers—so, e.g., if a, but not b, is a multiple of p, then a+b and a-b are not multiples of p.
The easiest case is where b is itself a small prime number like 17 or 13. Why 17 and 13? Because the number ends in 3, so subtracting something ending in 3 or adding something ending in 7 will give us (an easy-to-deal-with factor of 10, and) something nicely smaller. In some cases it’s easier to remove digits from the start of the number rather than the end; for a trivial example, 1033 isn’t a multiple of 103 because it’s 1030 + 3.
Let’s do 1033 a bit more thoroughly. It’s between 32^2=1024 and 33^2=1089, so we need to check primes up to 31. 1033=1050-17 rules out 2,3,5,7,17. 1033=1020+13 rules out 2,3,5,13,17. 1033=1000+33 rules out 2,3,5,11. (That’s all the primes up to 17 done, leaving 19,23,29,31.) 1033=1010+23 rules out 2,5,(101),23. At this point, actually, I’d try dividing by 19,29,31, but let’s carry on. For 31 we’ll subtract 93: 1033=940+93, and 940=2.2.5.47 so we’ve ruled out 31. For 19 we’ll subtract 950, leaving 83 which is prime, so 19 is ruled out. For 29 I suppose the best we can do is to subtract 870, leaving 163 which I happen to know is prime because of exp(pi sqrt(163)) but in any case clearly isn’t a multiple of 29. So we’re done and 1033 is prime. And I didn’t factorize 1033 unless proving something is prime by a roundabout route counts as factorizing it. If one of these things had turned out to have the same prime number dividing both summands, there’d still have been extra work to do to get the quotient.
Right. And, indeed, when I need to check in my head whether a smallish number like 1033 is prime, most of what I do isn’t factoring. E.g.: 1033+17 = 1050 = 50.21, ruling out {2,3,5,7,17} in a single go but not identifying any factors or (even approximate) quotients. 1033-13 = 1020 = 20.51, ruling out {2,3,5,13,17} instead. Etc.
I also assumed that Eliezer’s intention was that you shouldn’t be doing this sort of thing.
[EDITED to fix formatting screwage—asterisks treated as markup rather than multiplication—my apologies for any mystification this caused.]
I’m curious, what’s the method you’re using there?
(Initial remark: damn, I see that what I wrote got screwed up by asterisks getting treated as markup characters; perhaps everything would have been clear without that. Will fix once I’ve finished writing this.)
I’m not sure it really warrants dignifying with the term “method”, but:
The relations I’m looking for are of the form n=a+b or n=a-b where a,b (1) are easy to factor because they’re products of small primes, and (2) have no common factor. In that case, you know that n isn’t a multiple of any of those prime numbers—so, e.g., if a, but not b, is a multiple of p, then a+b and a-b are not multiples of p.
The easiest case is where b is itself a small prime number like 17 or 13. Why 17 and 13? Because the number ends in 3, so subtracting something ending in 3 or adding something ending in 7 will give us (an easy-to-deal-with factor of 10, and) something nicely smaller. In some cases it’s easier to remove digits from the start of the number rather than the end; for a trivial example, 1033 isn’t a multiple of 103 because it’s 1030 + 3.
Let’s do 1033 a bit more thoroughly. It’s between 32^2=1024 and 33^2=1089, so we need to check primes up to 31. 1033=1050-17 rules out 2,3,5,7,17. 1033=1020+13 rules out 2,3,5,13,17. 1033=1000+33 rules out 2,3,5,11. (That’s all the primes up to 17 done, leaving 19,23,29,31.) 1033=1010+23 rules out 2,5,(101),23. At this point, actually, I’d try dividing by 19,29,31, but let’s carry on. For 31 we’ll subtract 93: 1033=940+93, and 940=2.2.5.47 so we’ve ruled out 31. For 19 we’ll subtract 950, leaving 83 which is prime, so 19 is ruled out. For 29 I suppose the best we can do is to subtract 870, leaving 163 which I happen to know is prime because of exp(pi sqrt(163)) but in any case clearly isn’t a multiple of 29. So we’re done and 1033 is prime. And I didn’t factorize 1033 unless proving something is prime by a roundabout route counts as factorizing it. If one of these things had turned out to have the same prime number dividing both summands, there’d still have been extra work to do to get the quotient.