Let $x,n$ be integers such that $x < n$.

Let $x\#$ be the primorial of $x$ so that $6\# = 5\# = 30$ and $7\# = 210$

Let gcd$(a,b)$ be the greatest common divisor of $a$ and $b$.

Let $S(x,n)$ be the set of integers such that $s \in S(x,n)$ if and only if gcd$(s,x\#)=1$ and $s \le n$

Let $|S(x,n)|$ be the number of elements in the set $S(x,n)$

Let $p$ be the least prime greater than $x$.

Does it follow that there are at least $\left\lfloor\left(\frac{p-1}{p}\right)|S(x,n)|\right\rfloor$ elements relatively prime to $p$ in $S(x,n)$?

Here are some examples:

  • $S(3,35) = \{1,5,7,11,13,17,19, 23, 25, 29, 31, 35\}$

There are at least $\left\lfloor\left(\frac{4}{5}\right)12\right\rfloor = 9$

  • $S(5,49) = \{1,7,11,13,17,19,23,29,31,37,41,43,47,49\}$

There are at least $\left\lfloor\left(\frac{6}{7}\right)14\right\rfloor = 12$

I suspect the answer is no.

Could someone provide an example of $x,n$ where there are less than $\left\lfloor\left(\frac{p-1}{p}\right)|S(x,n)|\right\rfloor$ elements relatively prime to $p$ in $S(x,n)$


I reworded the question to fix a mistake in my wording.

I had said "greater than $p$", I had meant to say "relatively prime to $p$.".

My examples had always shown "relatively prime to $p$". I had excluded elements that had $p$ as a divisor.

  • $\begingroup$ Closely related to $y$-rough numbers below $x$. $\endgroup$ – Peter Jan 27 at 16:30
  • 2
    $\begingroup$ At first $\sum_{m \le n, gcd(m,\# x)=1} 1 = \sum_{d | \# x} \mu(d) \lfloor n/d \rfloor = \sum_{d | \# x} (\mu(d) n/d +O(1))$ $ = n\prod_{p \le x} (1-1/p) + O(\tau(\# x)) = n\frac{e^{-\gamma} }{\log x}(1+O(\frac{1}{\log^2 x}))+O(e^{\epsilon x})$ which answers for $n $ larger than $e^{\epsilon x} \log x$. For $n$ small you need other arguments. For $n\in (x,x^2]$, $\sum_{m \le n, gcd(m,\# x)=1} 1 = \pi(n)-\pi(x)$ and you can use things like the PNT or upper bounds for the prime gap. $\endgroup$ – reuns Jan 29 at 20:21
  • $\begingroup$ $S(3,4)=\{ 1 \}$ so $ \lfloor 4/5 \times \mid S(3,4) \mid \rfloor=0< 5$ ... what did I miss ? $\endgroup$ – Donald Splutterwit Jan 30 at 0:59
  • 1
    $\begingroup$ I don't get it; isn't it true that $S(x,n)\cap [1,p-1]=\{1\}$, so all elements of $S(x,n)-\{1\}$ are greater than $p$ ? $\endgroup$ – user120527 Jan 30 at 10:45
  • $\begingroup$ To be clear, there are many elements of $S(x,n) - \{1\}$ which are not relatively prime to $p$ since $\{p, p^2, p^3, \dots\} \subset S(x,n)$ if $p^3 \le n$ $\endgroup$ – Larry Freeman Jan 30 at 22:17

there are at least $\left\lfloor\left(\frac{p-1}{p}\right)|S(x,n)|\right\rfloor$ elements relatively prime to $p$ in $S(x,n)$.

I wrote a program to verify this conjecture for $x=p-1$, $p\le 100$ and $n\le 1000$. It fails for all $p$ from $11$ to $59$, the first time for $p=11$ and $n=473$ with $\left\lfloor\left(\frac{p-1}{p}\right)|S(x,n)|\right\rfloor=99$ and $98$ elements relatively prime to $p$ in $S(p-1,n)$.

Below I add the main procedure of the program (in Delphi 5):

TForm1.Button1Click(Sender: TObject);
 Prime:array[1..NumberOfPrimes]of Integer=(2,3,5,7,11,13,17,19,23,29,31,37,41,

for l:=1 to NumberOfPrimes do begin
for n:=1 to Maxn do begin
 for j:=1 to l-1 do if (n mod prime[j])=0 then goto 0;
 inc (SAll);
 if ((n mod p)=0) then inc(SDiv);
if trunc((p-1)*SAll/p)>(SAll-SDiv) then
 Memo1.Lines.Add(IntToStr(n)+' '+IntToStr(trunc((p-1)*SAll/p))+' '+
  • 1
    $\begingroup$ Awesome. Thanks very much! $\endgroup$ – Larry Freeman Feb 3 at 17:02
  • $\begingroup$ @LarryFreeman Thank you for your kind words. I expect that there are no errors in the program, because it is short, simple, and clear and I tested it with small values. Anyway, the proposed counterexample can be easily checked (it took me several minutes to wrote the program). $\endgroup$ – Alex Ravsky Feb 3 at 17:09
  • 1
    $\begingroup$ I verified the result before accepting your answer. :-). $\endgroup$ – Larry Freeman Feb 3 at 17:31

Not an example, just some thoughts on what kind of example to look for (though you might already know this):

Some prime $p$, such there are less than $p - 1$ primes between $p$ and $p^2$.

If $ x= p$ and $n = p^2$, and there are $ k $ primes between $p$ and $p^2$, meaning $ k $ elements that are co-prime to $p $ in $s(x, n)$, we have

$\left\lfloor\left(\frac{p-1}{p}\right)|S(x,n)|\right\rfloor = \left\lfloor\left(\frac{p-1}{p}\right)|(k + 2)|\right\rfloor$

It holds that:

$k + 2 > \left\lfloor\left(\frac{p-1}{p}\right)|k + 2|\right\rfloor > k \iff \left\lfloor\left(\frac{p-1}{p}\right)|k + 2|\right\rfloor = k + 1 $ $\iff \frac{p-1}{p}(k+2) \geq (k+1) \iff k+ 2 - \frac{1}{p}(k + 2) \geq k + 1 $ $\iff 1 \geq \frac{k + 2}{p} \iff p \geq k +2 $

Also, after $p^2$, the next element of $s(x, n)$ that is not co-prime with p is $p \cdot q$, where q is the next prime after p. Then if $ n = p \cdot q $, we have:

$k + 3 > \left\lfloor\left(\frac{p-1}{p}\right)|s(x,n)|\right\rfloor = \left\lfloor\left(\frac{p-1}{p}\right)|k + 3|\right\rfloor > k \iff 2\cdot p - 3 \geq k$.

Other notes:

If $|s(x,n)| = 1 $ the claim clearly holds. It also holds if $|s(x,n)| = 2 $, since from Bertrands Postulate there must be a prime q greater than p but smaller than $p^2 \geq 2p$. As $p^2$ is the next number after p in $s(x,n)$ that is NOT relatively prime to p, $s(x,n)$ is only interesting if $n \geq p^2$.

  • 1
    $\begingroup$ Yes, those are my assumptions with the added observation that for $x \ge 4$, there is always at least $x$ primes between $x$ and $x^2$. See the argument here for $x > 30$ and the rest can be verified independently. $\endgroup$ – Larry Freeman Feb 1 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.