Return to Answer

Given any odd prime $p$ we can use Dirichlet to find another prime $q$ congruent to a multiplicative generator modulo $p$. Then letting $n=pq$, we see that we can't improve the $\frac{n}{2}$ bound significantly for a product of two primes.

For a product of three primes e.g., $2pq$, we can do a little better because solving the problem for $n=pq$ automatically produces a solution for $2pq$ as well.

Given any odd prime $p$, let $r=\lfloor p/2\rfloor-1$. We work in $\mathbb{Z}_p^\ast$ and consider the elements $\pm 1,\pm 1/2,\pm 1/3,\ldots \pm 1/r$. By the pigeonhole principle there is a residue $\bar q$ which is not on the list. We then use Dirichlet to find a prime $q\in\mathbb{N}$ congruent to $\bar q$ modulo $p$. Then letting $n=pq$, we see that we can't improve the $\frac{n}{2}$ bound significantly for a product of two primes.

For a product of three primes e.g., $2pq$, we can do a little better because solving the problem for $n=pq$ automatically produces a solution for $2pq$ as well.

Given any odd prime $p$ we can use Dirichlet to find another prime $q$ congruent to $1$ modulo $p$. Then letting $n=pq$, we see that we can't improve the $\frac{n}{2}$ bound significantly for a product of two primes.

For a product of three primes e.g., $2pq$, we can do a little better because solving the problem for $n=pq$ automatically produces a solution for $2pq$ as well.

Given any odd prime $p$ we can use Dirichlet to find another prime $q$ congruent to a multiplicative generator modulo $p$. Then letting $n=pq$, we see that we can't improve the $\frac{n}{2}$ bound significantly for a product of two primes.

For a product of three primes e.g., $2pq$, we can do a little better because solving the problem for $n=pq$ automatically produces a solution for $2pq$ as well.

The $\frac{n}{2}$ bound does not work in general, for example when $n=p^k$ for $p$ an odd prime.

Given any odd prime $p$ we can use Dirichlet to find another prime $q$ congruent to $1$ modulo $p$. Then letting $n=pq$, we see that we can't improve the $\frac{n}{2}$ bound significantly for a product of two primes.

For a product of three primes e.g., $2pq$, we can do a little better because solving the problem for $n=pq$ automatically produces a solution for $2pq$ as well.