# Existence of a large divisor of the product of all primepowers in the interval [p/2, p], with the divisor restricted to some moduloclass

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}$.

-
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))}$.