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

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.

• Closely related to $y$-rough numbers below $x$. – Peter Jan 27 at 16:30
• 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. – reuns Jan 29 at 20:21
• $S(3,4)=\{ 1 \}$ so $\lfloor 4/5 \times \mid S(3,4) \mid \rfloor=0< 5$ ... what did I miss ? – Donald Splutterwit Jan 30 at 0:59
• 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$ ? – user120527 Jan 30 at 10:45
• 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$ – 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);
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
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
IntToStr(SAll-SDiv));
0:end;
end;
end;

• Awesome. Thanks very much! – Larry Freeman Feb 3 at 17:02
• @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). – Alex Ravsky Feb 3 at 17:09
• I verified the result before accepting your answer. :-). – 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$$.

• 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. – Larry Freeman Feb 1 at 21:34