MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $p_i$ be the i-th prime number and $h_k:= p_{i+1}p_{i+2}\cdots p_{i+k}$. Is there for every $i\in \mathbb{N}$ a $k\in \mathbb{N}$ such that $h_k\equiv 1 \mod p_1p_2\cdots p_i$?

share|cite|improve this question
Not sure if this can be proved but I would be surprised if it were not true. Perhaps you know this already, but for h(j,k) the product of the i + j th to the i +j + k th prime there would be a short argument that show h(j,k) will be congruent one (even with bounds on j and k). – quid Feb 1 '12 at 15:53
Perhaps I should add something to my preceeding comment as otherwise it could seem silly (taking k=0 if one allows and just applying Dirichlet; or some modification of this argument). If one defines rj as the residue of p(i+j) modulo the product of the first i primes, then all the rj are invertible classes. So one has an infinite sequecence in the finite group of invertible residue classes modulo the product. Except some bias due to size at the start these elements should be essentially 'random'. So the hj arises by multiplying some element of... – quid Feb 1 '12 at 16:06
...a finite abelian group with a 'new' and 'random' element. Eventually this 'new' element should just happen to be the inverse of the product of the preceeding ones (at each step one has a constant probabilty for this to happen). I have however no idea if one can make this rigorous. Yet what is definitely the case is that after some explict number of steps one has a collison of an hk with an hk' (as there are only fin many choices) and 'cancelling' the common start one gets what I claimed in an elementary way. – quid Feb 1 '12 at 16:10
so, the conjecture would be that the set of $k$'s such that $h_k$ solves that congruence has density $\frac{1}{(p_1-1)\cdots(p_i-1)}$? This would be nice! – Valerio Capraro Feb 1 '12 at 16:40

It seems sure that it is true but will never be proven. Let me give a much stronger conjecture which would imply this one. Let $m$ be some modulus such as $m=p_1p_2\cdots p_i$ and let $r_j=p_j \mod{m}.$ Once $r_j$ is larger than the largest prime divisor of $m$ there are $\phi(m)$ values that $r_j$ can take. One would like to say that the sequence $r_k,r_{k+1},r_{k+2},\cdots$ behaves like a fair random die with $\phi(m)$ sides. However, as stated that is not true.

We do know that the proportion of primes taking any given value is asymptotically $1/\phi(m).$ Looking at the prime number race between $4m+1$ and $4m+3$, the class $4m+1$ is in the lead infinitely often however the proportion of the time that it is in the lead goes to 0. It first pulls into the lead at the prime 26861 then loses it at 26863 and next pulls into the lead at various values between 616,000 and 634,000 and then not again until past 12,300,000. I imagine that similar things are true for any modulus $m.$

Also, in the short run the values are nowhere close to being independent. For example $r_{s+1}=r_s$ is not possible until $s$ is large: For $n \gt 3$ There is a prime between $n$ and $2n-2$ so we certainly can't have $r_s=r_{s+1}$ until $p_s \ge m.$ In fact there is a prime between $x$ and $x(1+1/16597)$ provided that $x \gt 2,010,760$ so we would need to have $p_s \gt 16597m$ provided that $m$ was large enough.

The conjecture is (in part) that in the long run the proportion of times this (or any other possible pair ) happens is $1/\phi(m)^2.$

Here is the stronger conjecture (for which I claim no originality, It is either too naive or else fairly common, I just couldn't find it stated in exactly this form:)

Let $a_0,a_1,a_2,\cdots,a_t=\mathbf{a}$ be any sequence of residues relatively prime to $m$, then the proportion of $k$ such that $r_k,r_{k+1},\cdots,r_{k+t}=\mathbf{a}$ is asymptotically $1/\phi(m)^{t+1}.$

Were this true then one could have $h_k,h_{k+1},\cdots,h_{k+\phi(m)}$ walk through all the possible residues in any desired order (a small detail is left to the reader.)

However this would take a fantastically long time and much longer than is likely to be needed to get some $h_k$ be $1\mod{m}.$

share|cite|improve this answer

Your Answer


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.