Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to find examples of "small" numbers which are known to be composite, but for which no prime factors are known. According to this website the number $109!+1$ is a composite number of 177 digits, but no factors are known. However, I can't find anything more up-to-date; maybe that number has been factored now; maybe there is a smaller unfactored composite number.

Anyway: does anybody know the smallest known composite number for which no prime factors are known?

--

Addendum. With further exploration of the above pages I've found that the Wolstenholme number which is the numerator of

$$\sum_{k=1}^{163}\frac{1}{k^2}$$

has 138 digits and is composite, and no factors are known, as of July 16, 2012. This is the smallest such number I've found so far.

--

More: In the most recent (third) edition of the book of factorization of Cunningham numbers ($b^n\pm 1$) by Brillhart et al, the number $2^{1462}+1$ includes in its factorization a 130-digit composite number which at the time of publication had not been factored.

share|improve this question
    
Not sure how to find smallest; various searches, Mersenne and Fermat numbers, regularly produce numbers which can be proved composite but for which no factors are known by anyone. There are quite a number of such searches, different purposes. Also, sometimes one factor of something is known, but then a known composite but unfactored part remains. –  Will Jagy May 12 at 2:21
add comment

3 Answers 3

Here's a number of 50 digits:

$$84286144766718574585896327097775856948442086719729$$

It's a good bet that nobody has yet considered this particular number (just because there are so many 50-digit numbers, and this one was chosen randomly).

Maple says it's composite, but since nobody else has considered this number and I don't know the factors, it's an example of a number that is "known to be composite, but for which no prime factors are known."

Oops: now I do know them: $178601959352247480503$ and $471921725116606004970765902743$. But you get the idea...

share|improve this answer
    
I don't know.This number might have been factored by someone while prime searching(ps:I don't know the methods of prime searching). –  rah4927 May 12 at 3:17
4  
Let's say there are $10^8$ computers working on factoring, and each has attempted one $50$-digit number every millisecond for the past $40$ years. That would be about $10^{20}$ such attempts in all. But there are $9 \times 10^{49}$ $50$-digit numbers... –  Robert Israel May 12 at 3:39
    
50 digits is too small, because any modern factoring algorithm can factorize such a number in a few seconds. (I got Sage to factor 842...729 from above which it did very quickly). I'm not sure how to best phrase my question; it's true that the factors of most numbers are unknown simply because relatively few numbers have been factorized. On the other hand some numbers are trivially factorizable (small numbers, numbers with lots of small factors), and others aren't. –  Alasdair May 12 at 4:35
1  
@Alasdair: there is a big difference between factors that are known and factors that can be found. This is the point of both this post and mine. Yes you can factor much larger numbers than this easily, but there are lots of numbers of this size that nobody has wanted to factor. If you want an unfactored composite, the easiest way is to find a small number you can show is composite that hasn't been factored. I suspect even my 20 digit example had never been factored before now. –  Ross Millikan May 12 at 4:43
    
@Alasdair: Perhaps what you really want is something like: the smallest number that is known to be composite but [name your favourite program] is unable to factor in [name a time limit] on [specify the hardware]. –  Robert Israel May 12 at 5:25
show 1 more comment

RSA numbers are semiprimes that are part of a challenge to factor them. They are known to be be composite because they were generated by multiplying two primes together.

It's hard to judge whether a number has been factored yet, someone could have done it in private. Publicly RSA-220

2260138526203405784941654048610197513508038915719776718321197768109445641817 9666766085931213065825772506315628866769704480700018111497118630021124879281 99487482066070131066586646083327982803560379205391980139946496955261

is within our current computational power but hasn't been factored yet. RSA-240 is beyond our capability currently (though it might be being factored right now)

1246203667817187840658350446081065904348203746516788057548187888832896668011 8821085503603957027250874750986476843845862105486553797025393057189121768431 8286362846948405301614416430468066875699415246993185704183030512549594371372 159029236099

share|improve this answer
    
These are both larger than the example cited in the question. –  Ross Millikan May 12 at 2:17
    
@RossMillikan Unless I read the examples wrong, are all these factored? –  qwr May 12 at 2:23
    
No, OP says they have no known factors. –  Ross Millikan May 12 at 2:33
add comment

There are a huge number of composite numbers that have unknown factors, most because nobody has tried. I'll bet nobody had factored $20754285234059597221$ before I just tried PrimeQ(20754285234059597221) at Alpha. Unfortunately, Alpha not only told me it isn't prime, it factored it as $22892731 \times 906588437791$. I found it by typing a bunch of numbers on the keyboard, then appending seven zeros and finding the next number smaller that was $1 \pmod {19!!}$ I would just take some number with $20$ digits, find a near one that is $1 \pmod {19!!}$ and try the Fermat test at increments of $19!!$ until you find one that is composite. I'll bet it has never been factored (but could be easily). The $19!!$ guarantees it does not have a factor below $19$.

share|improve this answer
    
@Hurkyl: but there are so many of them it is likely that nobody has thought about a given one to the point of factoring it. I didn't say it was hard to factor, just that factors were (until now) not known. –  Ross Millikan May 12 at 2:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.