Mathematics desk
< January 1	<< Dec \| January \| Feb >>	January 3 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 2

Modular arithmetic into which the primes fit neatly

Hello. I'm thinking about numbers N such that the first N primes are pairwise non-congruent modulo N, that is, such that the modulo N function is a bijection between the first N primes and Z_N. The possibilities 0, 1 and 2 satisfy this, but with Mathematica I have searched all the numbers up to 10000 and not found any others. It seems less likely for large N, since there are lots more primes that need to serendipitously line up, but I can't see how I might prove that none others exist. Anybody have any ideas? Cheers, Maelin (Talk | Contribs) 07:22, 2 January 2009 (UTC)[reply]

Let's see. Candidates for N have to be primes themselves, because only for prime N can find a prime to fill the 0 modulo N slot - that prime is N itself. So we have a bunch of primes between 2 and N that are equal to themselves modulo N, then N = 0 modulo N, then a bunch of primes between N and 2N that are each equal to an even number modulo N. So as long as you avoid prime N such that N+2 is also prime, you are okay up to 2N. You then want 2N+p to be composite for all primes p less than N - otherwise you have two primes, p and 2N+p, that are both equal to p modulo N. Similarly, 4N+p has to be composite for all primes p less than N, as does 6N + p etc. As you say, this becomes less and less likely as N becomes larger. This is not yet a proof, but it is a heuristic argument that an N with these properties is unlikely to exist. Gandalf61 (talk) 13:03, 2 January 2009 (UTC)[reply]

There is no N < 5×10¹¹ and probably no N at all. In [1] and [2] I computed for all values of 2N < 10¹² (also for all composite N) the smallest prime p such that 2N+p is also prime. The largest of these smallest primes was p = 3307 for 2N = 496562420542, corresponding to N = 248281210271 which happens to be prime. 3307 is the 465th prime out of 9,854,584,613 primes below that N. PrimeHunter (talk) 14:10, 2 January 2009 (UTC)[reply]