Counting integers less than $n$ that are relatively prime to $x\#$

Question

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

---

Edit:

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.

Answer 1

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);
label
 0;
const
 NumberOfPrimes=25;
 Maxn=10000;
 Prime:array[1..NumberOfPrimes]of Integer=(2,3,5,7,11,13,17,19,23,29,31,37,41,
 43,47,53,59,61,67,71,73,79,83,89,97);
var
 n,j,l,p:Integer;
 SAll,SDiv:Integer;

begin
for l:=1 to NumberOfPrimes do begin
Memo1.Lines.Add(IntToStr(prime[l]));
SAll:=0;
SDiv:=0;
p:=prime[l];
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))+' '+
 IntToStr(SAll-SDiv));
0:end;
end;
Memo1.Lines.Add('Done');
end;

Answer 2

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