Find the smallest prime factor of 100!+11?

Question

Sorry. The right problem should be 100!+1

Ana,
I know you are math professor. Thank you for sharing your opinion on this problem. Obviously the smallest prime should be larger than 100. But to find it is really hard.

Answer 1

The smallest prime divisor of 100! + 1 is 101.

Here's proof, assuming you know some basic modular arithmetic and Wilson's theorem:

Wilson's theorem states that p is a prime if and only if (p - 1)! = -1 (mod p). 101 is a prime, so by Wilson's theorem we have that 100! + 1 = (101 - 1)! + 1 = -1 + 1 = 0 (mod 101). Therefore 101 divides 100! + 1. To show that 101 is the smallest prime divisor, consider any prime p < 101, and look at 100! + 1 mod p. p appears in the product 100!, so it follows that 100! + 1 = 0 + 1 = 1 (mod p), i.e. p does not divide 100! + 1.

If you've never seen Wilson's theorem before, it requires a good amount of work to prove. Any basic number theory course would probably go through a proof of it.

Answer 2

Since 100! has 11 as a factor, it's easy to see that 11 is a factor of (100! + 11). To see if it's the smallest, it's easy enough to test the other prime numbers less than 11. "2" can't be factor, since 100! will be an even number and 100! + 11 will be an odd number. Likewise, since 100! has both 5 and 7 as factors, and since neither is a factor of 11, then 100!+11 can't have 5 nor 7 as factors. Therefore, 11 is the lowest.

Notice that just because you have a number plus a prime number, it doesn't necessarily mean that the smallest prime factor is the second number, nor that it must divide into both. For example, 3 is the smallest prime factor of (4+5), even though it divides neither 4 nor 5.

Answer 3

The answer is 101. If you work mod 101, then 100 = -1 So to prove that 100! +1 = 0, you need to prove that 99! = 1. For that it is enough to show that the numbers between 2 and 99 can be put in 49 pairs (p,q) such that pq=1. But Z/101Z is a field. So each number between 2 and 99 has a an inverse in the same range and the problem reduces to showing that no number is its own inverse that is p^2=1. This can be checked easily because 102,203, 304 up to 2425 and 2526, are not squares and that's it. Indeed if there is one number such that p^2=1, there must be another one, hence (p-q)x(p+q) is a multiple of 101 so p+q = 101 and one of two is less than 50.

Answer 4

Well, since I was unable to solve it, no matter how hard I tried, I asked a friend of mine that is really a bright mind. This is his answer

Take care

Ana

Ana Flores asked:
>
> Whats the smallest prime factor of 100! + 1?
>
I don't think there's an intelligent method to solve that. Maybe the
only way is by brute force and ignorance: write the big number, then
start looking for prime factors. It might take some time :-)

Some computer languages can handle "infinite" precision integers.

100! =
9332621544394415268 1699238856266700 4907159682643816 2146859296389521 7599993229915608 9414639761565182 8625369792082722 3758251185210916 8640000000000000 00000000000

Unless I did something wrong, the first prime factor is 101.

The test for being a divisor of 101 is trivial: a decimal number ABCDEFGH....
is divisible by 101 when ABCD + EFGH + ... is divisible by 101.

So, it seems that 100! + 1 is divisible by 101.

Hmmm... I think (p-1)! + 1 is always divisible by p, whenever p is prime... So
there _is_ an intelligent way to answer the question

Answer 5

11

Answer 6

Smallest prime factor will be 11

Let n = 100!

n, by definition, is divisible by all numbers between 1 and 100 inclusive.

if n divides by 2, n + 11 doesn't (as 11 doesn't divide by 2)
if n divides by 3, n + 11 doesn't (as 11 doesn't divide by 3)
same method to discount 5 and 7

But 11 does divide by 11, so 100! + 11 divides by 11

Answer 7

It would have to be 11 since 11 clearly divides 11 and 100!

Answer 8

There are three, including 7, 77, and 91.

Answer 9

7854590063594865046349577357939735626842827

p.s. I'm so glad I didn't plump for 11.

Answer 10

2,2,5,5