# Regarding Wilson's Theorem

• Jul 14th 2010, 05:52 AM
Bingk
Regarding Wilson's Theorem
I was just wondering something

(p-1)! = -1 mod p

I was investigating the number (p-1)! + 1, which is divisible by p. I was wondering if n = ((p-1)! + 1)/p, then does the prime factorization of n consists of primes all of which are to the power of 1 (except for the case of p = 2, since n = 1)?

I couldn't really test much because of the factorial, it makes the numbers huge ... I tried till p = 37 ... after that I get problems with factoring the huge number generated by the factorial ...

• Jul 14th 2010, 07:44 AM
chiph588@
This looks like an interesting result! Wolfram alpha would be able to factor what you're looking for.
• Jul 14th 2010, 08:31 AM
Bingk
Thanks!! That's a neat site :)

Wolfram worked up to p=59 (except for p=47, not sure why, might be an internet problem on my part), after that, it doesn't work (at least up to p=101) ... but at least it's giving me hope. Everything I've tested so far seems to work :)

I was thinking that it might be a potential way to generate candidates for the largest prime :), but then again, I'm not familiar with how it's usually done, hehehe.

Any other resources I could tap?
• Jul 14th 2010, 09:04 AM
chiph588@
Quote:

Originally Posted by Bingk
Thanks!! That's a neat site :)

Worked up to p=59 (except for p=47, not sure why, might be an internet problem on my part), after that, it doesn't work (at least up to p=101) ... but at least it's giving me hope. Everything I've tested so far seems to work :)

I was thinking that it might be a potential way to generate candidates for the largest prime :), but then again, I'm not familiar with how it's usually done, hehehe.

Any other resources I could tap?

I'm not sure this would be the best way to find the largest known prime. Google GIMPS to learn more about the preferred method to date.

I'm more interested in why $\displaystyle (p-1)!+1$ seems to be square free!
• Jul 14th 2010, 01:31 PM
Matt Westwood
Good page on wikipedia which you might like to start at

Wilson's theorem - Wikipedia, the free encyclopedia
• Jul 14th 2010, 04:46 PM
Bingk
Um, it's actually, $\displaystyle \displaystyle{\frac{(p-1)!+1}{p}}$ that is square free. for 5 and 13, you'll see that the prime factors of $\displaystyle (p-1)!+1$ involves $\displaystyle 5^2$ and $\displaystyle 13^2$
• Jul 15th 2010, 02:20 AM
Bacterius
$\displaystyle p = 47$ works. I think we're not going to be able to go much further than $\displaystyle p = 101$, as factorization cannot be done efficiently. However, I wonder if some polynomial time algorithm exists to check whether an integer is square-free ? I don't think so but perhaps ...
• Jul 15th 2010, 02:26 AM
Bacterius
Quote:

I was thinking that it might be a potential way to generate candidates for the largest prime
Don't think so either, the numbers don't seem deemed to be prime with high probability at all ... however their prime factorization is quite .. ah .. unusual. This has to be explored.
• Jul 15th 2010, 03:10 AM
Bacterius
Here's a mathematical headstart anyway :

Theorem

$\displaystyle (p - 1)!$ is not squarefree for prime $\displaystyle p > 5$.

Proof

Let $\displaystyle q$ be the greatest prime number that satisfies $\displaystyle 2q < p - 1$. Then $\displaystyle kq | (p - 1)!$ for $\displaystyle k \in \{1, 2\}$, thus $\displaystyle q^2 | (p - 1)!$. Since no $\displaystyle q$ exists for $\displaystyle p \leq 5$, we need $\displaystyle p > 5$.

____________________

Maybe someone can put a condition on "if $\displaystyle x$ is not squarefree then $\displaystyle x + 1$ is squarefree", which could potentially prove the conjecture if the condition is cleverly chosen ...
• Jul 15th 2010, 03:47 AM
tonio
Quote:

Originally Posted by Bacterius
Here's a mathematical headstart anyway :

Theorem

$\displaystyle (p - 1)!$ is not squarefree for prime $\displaystyle p > 5$.

Proof

Let $\displaystyle q$ be the greatest prime number that satisfies $\displaystyle 2q < p - 1$. Then $\displaystyle kq | (p - 1)!$ for $\displaystyle k \in \{1, 2\}$, thus $\displaystyle q^2 | (p - 1)!$. Since no $\displaystyle q$ exists for $\displaystyle p \leq 5$, we need $\displaystyle p > 5$.

____________________

Maybe someone can put a condition on "if $\displaystyle x$ is not squarefree then $\displaystyle x + 1$ is squarefree", which could potentially prove the conjecture if the condition is cleverly chosen ...

I don't know if there's some mistake on your theorem, but it is a rather trivial, boring one: $\displaystyle n!$ is not square free whenever $\displaystyle n\geq 4$, as it is trivially divisible by $\displaystyle 2^2=4$.

Tonio
• Jul 15th 2010, 04:16 AM
Bacterius
Quote:

Originally Posted by tonio
I don't know if there's some mistake on your theorem, but it is a rather trivial, boring one: $\displaystyle n!$ is not square free whenever $\displaystyle n\geq 4$, as it is trivially divisible by $\displaystyle 2^2=4$.

Tonio

You are right, I missed the trivial proof ... I must be tired.
I think my proof is all right though ... but it's obvious the trivial proof is a lot simpler !
• Aug 5th 2010, 01:53 PM
chiph588@
Wilson prime - Wikipedia, the free encyclopedia

Not exactly what you're after, but close.