Finding all integers $i$ such that $\frac{j}{\gcd(i,j)}$ is composite for some $j's$.

Question

Let $n$ be a positive integer and $p$ the largest prime $\le n$. Let $ j_1,j_2,\ldots,j_m\le n$ denote some positive composite numbers. Consider all integers $i$ with no prime factors larger than $p$: $$i=2^{a_2}3^{a_3}\cdots p^{a_p}; a_2,a_3,\ldots,a_p\in \mathbb{Z}_{\ge 0}.$$ Note that $i$ may be larger than $n$. Is it possible to find a formula for all $i$ such that for each $k$ with $1\le k\le m$, we have $$\frac{j_k}{\gcd(i,j_k)}$$ is composite?

Remark: The condition that $\frac{j}{\gcd(i,j)}$ is composite is equivalent to $j$ having at least two prime factors (including multiplicity) that $i$ does not have. E.g., $i=2^2, j=2^5; i=2*3, j=5*7; i=2^5, j=3^2$.

Examples:

(1) If $n=5$ and $j=4$, then in order for $\frac{4}{\gcd(i,4)}$ to be composite, we must have that $i$ is not divisible by $2$. So $i=3^{a_3}, a_3\ge 0$.

(2) If $n=6$ and $j_1=4, j_2=6$, then in order for $\frac{4}{\gcd(i,4)}$ to be composite we must have that $i$ is not divisible by $2$, and since $\frac{6}{\gcd(6,i)}$ is composite we have that $2$ and $3$ don't divide $i$. Therefore, $i=5^{a_5}, a_5\ge 0$.

Answer 1

Yes, it is possible : $$i_n=\prod_{q=s_n}^{t_n}{p_q}^{a_{p_q}}\tag1$$ where $i_n:=i,p_{t_n}:=p$, and $p_{s_n}$ is the smallest prime larger than $\frac n2$. Here, $p_u$ is the $u$-th prime.

Let us prove $(1)$ by induction on $n$.

Proof :

For $n=5$, we have $p_{s_5}=3,p_{t_5}=5,j=2^2$. In order for $\frac{2^2}{\gcd(i_5,2^2)}$ to be composite, we have to have $\gcd(i_5,2^2)=1$, so $i_5=3^{a_3}5^{a_5}$.

Suppose that $(1)$ holds for some $n$.

Here, let us separate it into cases :

• Case 1 : If $n+1$ is prime, then $p_{s_{n+1}}=p_{s_n}$ and $p_{t_{n+1}}=p_{t_n+1}=n+1$. Also, $j$s are the same. So, $i_{n+1}=i_n\cdot p_{t_{n+1}}^{a_{p_{t_{n+1}}}}$.

• Case 2 : If $n+1$ is composite such that $n+1=2p_{s_n}$, then $p_{s_{n+1}}=p_{s_n+1}$ and $p_{t_{n+1}}=p_{t_n}$. In order for $\frac{n+1}{\gcd(i_{n+1},n+1)}$ to be composite, $i_{n+1}$ is not divisible by $p_{s_n}$. So, $i_{n+1}=i_n/p_{s_n}^{a_{p_{s_n}}}$.

• Case 3 : If $n+1$ is composite such that $n+1\lt 2p_{s_n}$, then $p_{s_{n+1}}=p_{s_n},p_{t_{n+1}}=p_{t_n}$, and $\frac{n+1}{\gcd(i_n,n+1)}$ is still composite because the largest prime factor of $n+1$ is smaller than $p_{s_n}$. So, $i_{n+1}=i_n$.

So, in either case, $(1)$ holds for $n+1$. $\quad\blacksquare$

Answer 2

Let $J$ be the set of all $\frac{j_k}{q}$ such that $q$ is a prime dividing $j_k$. Then aren't the required numbers $i$ simply those positive integers with no prime factor greater than $p$ which are not multiples of any number in $J$?