Timeline for If $\binom{2p}{p}$ is $(-1)^{p-1} \bmod 2p+1$ is then $2p+1$ prime?
Current License: CC BY-SA 3.0
37 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 21, 2015 at 16:01 | vote | accept | Destiny freedom | ||
| Jun 14, 2015 at 10:29 | comment | added | YCor | @TheMaskedAvenger But the original question was so confusing that it was understandable that it was closed: indeed the conjecture was the same as above, but OP provides tests as an evidence for the conjecture, assuming that $2p+1$ is prime (instead of non-prime)! This led to 2 interpretations, one of which is the converse, which is an easy exercise and off-topic, the other being that the tests when $2p+1$ is prime are irrelevant (this is why I edited, removing the tests, and the question was subsequently reopened). | |
| S Jun 14, 2015 at 9:57 | history | suggested | Duchamp Gérard H. E. | CC BY-SA 3.0 |
grammar in the title, then cancelled misunderstanding from my side
|
| Jun 14, 2015 at 8:47 | review | Suggested edits | |||
| S Jun 14, 2015 at 9:57 | |||||
| Jun 14, 2015 at 8:36 | answer | added | YCor | timeline score: 8 | |
| Jun 13, 2015 at 19:17 | comment | added | The Masked Avenger | Mistakes will be made. If we are forgiving of ourselves, we can forgive others, and in such a cooperative spirit the mistakes made in this forum will be fixed. May the original poster collectively forgive us for getting it wrong and thank us for getting it right. | |
| Jun 13, 2015 at 16:52 | comment | added | Todd Trimble | @TheMaskedAvenger You are of course right; my first comment above was unfortunately a case of "shoot first, ask questions later". The relation to Wilson was supposed to be (well, at least under the proviso that $p!$ is prime to $2p+1$) that $(p!)^2 \equiv (-1)^{p-1}$ modulo $2p+1$. (There's a nice pictorial proof of that based on the graph representing the reciprocation relation on $\{2, \ldots, p\} + \{-2, \ldots, -p\}$ modulo $2p+1$.) But of course that proviso is true only if $2p+1$ is prime, leading to the same petitio principii objection I had raised in response to GH's argument. | |
| Jun 13, 2015 at 3:56 | comment | added | Destiny freedom | for $p=1093^2$,I found can by hand ,Note $1093^2|2^{1092}-1$,so $(2\cdot 1093^2+1)|(\binom{2\cdot 1093^2}{1093^2}+1$ | |
| Jun 13, 2015 at 2:26 | answer | added | Robert Israel | timeline score: 14 | |
| Jun 13, 2015 at 1:04 | comment | added | GH from MO | @RobertIsrael: You should post your counterexample as an answer so that the question can be closed. | |
| Jun 13, 2015 at 1:04 | comment | added | GH from MO | @TheMaskedAvenger: I see. The original post was written in terrible English, and I was sleepy as well. Now I understand what the OP meant. | |
| Jun 13, 2015 at 0:50 | comment | added | The Masked Avenger | @GHfromMO, that might have been your reading of the original post. Mine (and I imagine Todd's) is that the idea "2p+1 is prime" is a conjectured consequence. Of course, if 2p+1 is an assumption, then your observation holds, and Wilson is not needed to get the congruence. Then again, Robert Israel's example shows Wilson is of little use here. | |
| Jun 13, 2015 at 0:46 | comment | added | GH from MO | @TheMaskedAvenger: See my previous comment (to Todd Trimble). | |
| Jun 13, 2015 at 0:40 | comment | added | GH from MO | @ToddTrimble: The original assumption (before the question was edited) was that $2p+1$ is prime. In this case $p!$ is invertible modulo $2p+1$ and my argument works. What I wanted to point out is that Wilson's theorem is not needed. Note that for $p=4$, $2p+1=9$ is not prime. | |
| Jun 13, 2015 at 0:03 | comment | added | Robert Israel | @GerhardPaseman If $2p+1$ factorizes into powers of small primes, you can use results of Andrew Granville cecm.sfu.ca/organics/papers/granville/paper/binomial/html/… to compute it mod each of these prime powers, and then Chinese Remainder Theorem to put these together. | |
| Jun 12, 2015 at 23:53 | history | reopened |
Stefan Kohl♦ Lucia YCor Gerry Myerson Gjergji Zaimi |
||
| Jun 12, 2015 at 20:10 | comment | added | YCor | (Of course, I mean "only 3 such Catalan pseudoprimes", not "only 3 such primes"! these are $5907=3.11.179$, $1093^3$ and $3511^2$.) | |
| Jun 12, 2015 at 20:08 | comment | added | Gerhard Paseman | Can one quickly compute $\binom{2p}{p} \bmod (2p+1) $ using previous computed smaller values? Do I need to loop from 1 to p, or can I use the factorization of 2p+1 to speed up the computation? Gerhard "Often Looking For Faster Ways" Paseman, 2015.06.12 | |
| S Jun 12, 2015 at 19:50 | history | suggested | Gerhard Paseman | CC BY-SA 3.0 |
make the question title very specific
|
| Jun 12, 2015 at 19:42 | review | Suggested edits | |||
| S Jun 12, 2015 at 19:50 | |||||
| Jun 12, 2015 at 19:29 | comment | added | YCor | Sloane could recognize the sequence with the single term 5907 ($=2.2953+1$): the keyword seems to be "Catalan pseudoprime" or "Wilson spoilers":), see oeis.org/A163209; only 3 such primes are known (5907 and the squares of the two known Wieferich primes), see en.wikipedia.org/wiki/Catalan_pseudoprime. | |
| Jun 12, 2015 at 19:17 | history | edited | YCor | CC BY-SA 3.0 |
sorry, removed typo from title. To avoid pure noise I add the context.
|
| Jun 12, 2015 at 19:17 | comment | added | Stefan Kohl♦ | @RobertIsrael: Yes, and as far as I checked, this is the only counterexample where $p \leq 10000$. | |
| Jun 12, 2015 at 19:14 | review | Reopen votes | |||
| Jun 12, 2015 at 21:26 | |||||
| Jun 12, 2015 at 19:00 | comment | added | YCor | @RobertIsrael Nice, I checked only for $p\le 2000$...! I edited to remove the irrelevant tests (which concerns the converse: if $2p+1$ is prime then the divisibility holds, which as pointed out is an immediate exercise). I'm wondering why such composite $2p+1$ seem so rare. | |
| Jun 12, 2015 at 18:56 | history | edited | YCor | CC BY-SA 3.0 |
Removed irrelevant tests and improved English and title
|
| Jun 12, 2015 at 18:51 | comment | added | Robert Israel | The conjecture is false. Counterexample: $p = 2953$. | |
| Jun 12, 2015 at 18:28 | comment | added | Gerhard Paseman | Further, it is not clear that there isn't some p with 2p+1 composite in which 2p+1 divides the relation. It may follow from Wilson's Theorem, but I have not made the connection yet. Gerhard "Needs More Coffee, Of Course" Paseman, 2015.06.12 | |
| Jun 12, 2015 at 17:39 | comment | added | Todd Trimble | @GHfromMO The trouble is that some of the factors of $p!$ will be zero divisors mod $2p+1$, so you can't do the division by $p!$. For example, it's not true in the case where $p = 4$. | |
| Jun 12, 2015 at 17:31 | comment | added | The Masked Avenger | How does one get that 2p+1 is prime from your observation? | |
| Jun 12, 2015 at 17:20 | history | closed |
Andrés E. Caicedo GH from MO András Bátkai Andy Putman Lucia |
Not suitable for this site | |
| Jun 12, 2015 at 17:19 | review | Close votes | |||
| Jun 12, 2015 at 17:20 | |||||
| Jun 12, 2015 at 17:08 | history | edited | GH from MO |
edited tags
|
|
| Jun 12, 2015 at 17:07 | comment | added | GH from MO | @ToddTrimble: One doesn't even need Wilson's theorem, see my previous comment. | |
| Jun 12, 2015 at 17:07 | comment | added | GH from MO | Your conjecture is easy to prove, and it is not of research level. Indeed, modulo $2p+1$, $(2p)(2p-1)\dots(p+1)$ is congruent to $(-1)(-2)\dots(-p)=(-1)^pp!$, hence $(2p)(2p-1)\dots(p+1)/p!$ is congruent to $(-1)^p$. | |
| Jun 12, 2015 at 17:05 | comment | added | Todd Trimble | This is Wilson's theorem in disguise: en.wikipedia.org/wiki/Wilson%27s_theorem | |
| Jun 12, 2015 at 16:56 | history | asked | Destiny freedom | CC BY-SA 3.0 |