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

The title almost says it all;

Let $p$ be some large prime. Does there exist a $d$ such that the following three things hold?;

1) $d$ divides the product of all primepowers in the range $[p/2, p]$.

2) $\log d$ is asymptotically equal to $p/2$.

3) $d \equiv \dfrac{p+1}{2} \pmod{p}$.

share|cite|improve this question
Can you even show that there is d that satisfies conditions 1 and 2? Gerhard "Ask Me About System Design" Paseman, 2011.11.02 – Gerhard Paseman Nov 3 '11 at 0:41
Sure. Just take d to be the product of all the primepowers, which equals $e^{p(1 + o(1))}$ – Woett Nov 3 '11 at 1:16
Its that last assertion I suspect. I can believe e^(p - something small), but I am unsure that something small is a constant. Gerhard "Ask Me About System Design" Paseman, 2011.11.02 – Gerhard Paseman Nov 3 '11 at 1:44
It's not a constant.. But it's smaller than $\epsilon p$ for all $\epsilon > 0$ and large enough $p$. This is just equivalent to the prime number theorem, or am I doing something wrong? – Woett Nov 3 '11 at 1:55
I am doing rough mental calculations, so I may be coming up short; I feel that for p < 10^6, any such divisor d is strictly less than e^p, never mind its modulo class. I could move on to your question if you could provide a p and a d contrary to my feeling. Gerhard "Ask Me About System Design" Paseman, 2011.11.02 – Gerhard Paseman Nov 3 '11 at 2:02

The question seems very difficult. First of all, the product $P$ of all prime powers in $(p/2,p)$ is $e^{p(1/2+o(1))}$, see below for a proof. Therefore the question can be reformulated as follows: is there a subset $S$ of pairwise coprime integers such that (1) each element of $S$ divides a prime power in $(p/2,p)$, (2) the product over $S$ is $e^{o(p)}$ and congruent to $2P$ modulo $p$. Indeed any $d$ can be written as $P$ divided by the product over such an $S$ and vice versa.

Now the problem acquires a combinatorial flavor. One would look at the group $G=(\mathbb{Z}/p)^\times$, consider the subset $T\subset G$ represented by the divisors of the prime powers in $(p/2,p)$ and try to represent a particular residue class as a product of very few elements from $T$. Note that already $T$ is rather small, and $G$ is isomorphic to the cyclic group $\mathbb{Z}/(p-1)$ whose structure depends on the prime factorization of $p-1$. Even the simpler question seems difficult to answer: why does the subgroup generated by $T$ contain the residue class $2$ modulo $p$? Note that, by Artin's conjecture on primitive roots, this becomes the following question for infinitely many $p$'s: why does $T$ generate $G$?

To see my claim on the size of $P$, observe that $P$ is the same as the least common multiple of all prime powers in $(p/2,p)$, since each prime has at most one power there. On the other hand, the product $R$ of all primes in $(\sqrt{p},p/2)$ is coprime with $P$, hence $PR$ divides the least common multiple of all prime powers in $(1,p)$. This shows that $PR\leq e^{p(1+o(1))}$, whence also $P\leq e^{p(1/2+o(1))}$ by $R\geq e^{p(1/2+o(1))}$. On the other hand, $P$ is at least as large as the product of all primes in $(p/2,p)$ which is $e^{p(1/2+o(1))}$.

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.