Is it ever possible to determine that a number is composite without determining any specific factors? If so, how?

Wilson's Theorem is one way:

https://en.wikipedia.org/wiki/Wilson%27s_theorem

Yes. Find two numbers it does not divide, but whose product it divides.

https://en.wikipedia.org/wiki/Euclid%27s_lemma

Yes. For the hardest cases, it has been proven that determining whether a number is prime or composite is easier than finding the factors.

Well, to be nitty that technically isn't true because nobody has proven that factoring itself isn't easy, so they could be the same level of difficulty, though that would be a minor miracle. In practice, the AKS algorithm I linked above proves that you can always determine whether a number is prime or not without knowing a factor. In practice, it isn't actually used for that purpose because other algorithms work faster, but they either only work probabilistically or cannot be proven to work for all possible numbers. So in summary, cryptography that was based on telling whether a number is prime or not would be very easy to break with modern computers, while cryptography that is based on determining factors (as far as we know) isn't.

check if n-2 and n-4 are prime. if they are and n > 7 then it's a composite

Not certain if this is a true so I shall call it chezlaw's conjecture for now

Yes, 3 has a tendency to pop up as a factor quite often.

Yeah but if you think about it that way then you find a factor ��

This is true. If n-2 and n-4 are both prime, then n is divisible by 3. Just reduce mod 3.

Thanks for the replies. I'm not a math expert, so a lot of the info is way over my head. The reason I was asking is that my son came across the Euclid-Mullin Sequence, and we read that the 52nd number has not been determined yet because it requires finding the smallest prime factor of a 335-digit number. The 335-digit number is known to be composite, but nobody knows any of the factors yet. We were surprised to hear that was possible.

Can anyone explain how that could be known for such a large number? Wilson's Theorem and Euclid's Lemma both seem impractical in this case because of the number's size. We had read about the AKS Primality Test before I posted my question, but it made our heads explode. Can anyone explain it in a less technical way than the Wiki page?

I figure super computers can crunch the numbers when you have the rule clear. Quantum computers can do the factors when that time comes.

I think Wilson's Theorem would be a good one to understand the general principle of how these tests work. For many of primality tests (for example, the AKS primality test), you don't have finish the calculation to know that the number is composite.

Let's look at n = 5 using Wilson's Theorem:
-- 1*2 = 2 (mod 5)
-- 2*3 = 1 (mod 5)
-- 1*4 = 4 (mod 5)

And so we've shown that 5 is prime by finishing the calculation of 4!.

But let's look at n = 8 using Wilson's Theorem:

-- 1*2 = 2 (mod 8)
-- 2*3 = 6 (mod 8)
-- 3*6 = 2 (mod 8)
-- 4*2 = 0 (mod 8)

At this point, we can just stop because we know that it will be impossible for 7! to be equal to -1 (mod 8). And we've only done 4 out of the 7 calculations.

I don't know the specific tools used for the Euclid-Mullin value, but I would not at all be surprised if it was something that worked kind of like this.

https://en.wikipedia.org/wiki/Pockli...primality_test


You also have some very primitive tests like sum of digits being multiple of 9 then the number is too. eg 189 279 or 774632166111981

and other ones like

https://en.wikipedia.org/wiki/Divisibility_rule

The number a6aa321a21aaaa3a is composite for example

What is fun is to produce a formula that creates numbers with high probability of being primes.

like x^2+x+41


This polynomial has 26% chance to give you a prime as x ranges from 0 to 1 mil.

How about creating numbers with very many different prime factors? x positive integer.

x^(2*3*5*7*11*13)-1 for example?

as smaller example

3^(2*3*5*7) - 1=156842404291315292546856982848907511846394061457 30291592802676915731672495230992603635422093849215 048

FactorInteger[3^(2*3*5*7) - 1]=
={{2, 3}, {7, 2}, {11, 2}, {13, 1}, {31, 1}, {43, 1}, {61, 1}, {71,
1}, {211, 1}, {271, 1}, {421, 1}, {547, 1}, {1051, 1}, {1093,
1}, {2269, 1}, {4561, 1}, {6301, 1}, {24151, 1}, {368089,
1}, {1616161, 1}, {3369031, 1}, {3454081, 1}, {2664097031,
1}, {26751945361, 1}, {374857981681, 1}}



It also stands the chance to have very big prime factors.

Try this too for large factors potentially (you know by construction its composite with many factors)
FactorInteger[2^(2^8) - 1]=

={{3, 1}, {5, 1}, {17, 1}, {257, 1}, {641, 1}, {65537, 1}, {274177,
1}, {6700417, 1}, {67280421310721, 1}, {59649589127497217,
1}, {5704689200685129054721, 1}}

=1157920892373161954235709850086879078532699846656 40564039457584007913129639935

due to expansion of various power differences identities.

I support all of that