# How to express a coprime relation as a Congruence relation

When $$(n,k) \in \mathbb P^2$$, the following coprime relations appear to hold:

$$\gcd\Bigl(n^k,{\Bigl\lfloor \frac{p_n}{n} \Bigr\rfloor}^{k}\Bigr)=1$$

$$\gcd\Bigl(n^k,\Bigl\lfloor \frac{p_n^k}{n^k} \Bigr\rfloor,{\Bigl\lfloor \frac{p_n}{n} \Bigr\rfloor}^{k}\Bigr)=1$$

So the first part of my question is a request for a counter example for these, which are proving to be more and more elusive. As far I know thus far, they can also be extended to $$(n,k)$$ for which $$k$$ is any natural number.

however the later term in the greatest common divisor expression above $${\Bigl\lfloor \frac{p_n}{n} \Bigr\rfloor}^{k}$$, is not always coprime to $$\Bigl\lfloor \frac{p_n^k}{n^k} \Bigr\rfloor$$ and the strictly prime domain of $$(n,k)$$ is paritioned into two equivalence classes, the predicates for which are the coprimality of this pair of quantities and it's negation: $$\mathbb P^2=\mathbb P_1 \cup \mathbb P_2$$

$$\mathbb P_1={\Biggl\{(n,k):\gcd\Bigl(\Bigl\lfloor \frac{p_n^k}{n^k} \Bigr\rfloor,{\Bigl\lfloor \frac{p_n}{n} \Bigr\rfloor}^{k}\Bigr)=1}\Biggr\}$$

$$\mathbb P_2={\Biggl\{(n,k):\gcd\Bigl(\Bigl\lfloor \frac{p_n^k}{n^k} \Bigr\rfloor,{\Bigl\lfloor \frac{p_n}{n} \Bigr\rfloor}^{k}\Bigr) \gt 1}\Biggr\}$$

A sample of my numerical observations thus far are:

$$\mathbb P_1={\{(2, 2), (2, 3), (2, 5), (2, 7), (3, 2), (3, 3), (3, 5), (3, 7), (5, 5), (5, 7), (7, 2), (11, 2), (11, 5), (11, 7)}\}$$

$$\mathbb P_2={\{(5, 2), (5, 3), (7, 3), (7, 5), (7, 7), (11, 3), (13, 2), (13, 5), (17, 2), (19, 2), (19, 7), (29, 5)}\}$$

likewise,$$\Bigl\lfloor \frac{p_n^k}{n^k} \Bigr\rfloor$$ and $$n^k$$ are not always coprime, and the strictly prime domain of $$(n,k)$$ is paritioned into two equivalence classes, the predicates for which are the coprimality of this pair of quantities and it's negation:

$$\mathbb P^2=\mathbb P_1 \cup \mathbb P_2$$

$$\mathbb P_1={\{(n,k):\gcd\Bigl(n^k,\Bigl\lfloor \frac{p_n^k}{n^k} \Bigr\rfloor\Bigr)=1}\}$$

$$\mathbb P_2={\{(n,k):\gcd\Bigl(n^k,\Bigl\lfloor \frac{p_n^k}{n^k} \Bigr\rfloor\Bigr) \gt 1}\}$$

Numerical observations thus far are:

$$\mathbb P_1={\{(2, 3), (2, 5), (3, 2), (3, 3), (5, 2), (5, 5), (7, 2), (11, 2), (11, 5), (13, 2), (13, 3), (17, 2), (17, 3)}\}$$

$$\mathbb P_2={\{(2, 2), (3, 5), (5, 3), (7, 3), (7, 5), (11, 3), (13, 5), (23, 3)}\}$$

So the second part of my question, is how, and using what theorem, can I express the above as a congruence relation?

I have tried looking for the sequence of values of $$n$$ for various fixed values of $$k$$ on OEIS, but nothing has shown up. I'm not sure if my problem is important enough to put these sequences on there or not, it asks me to do so if I think they are of interest, but that's pretty subjective, I mean if it really is like face book and sequence popularity matters, anyway end of question.

• Note that the first relation implies the second. Also, $\gcd\Bigl(n^k,{\Bigl\lfloor \frac{p_n}{n} \Bigr\rfloor}^{k}\Bigr)=1$ for some $k$ if and only if $\gcd\Bigl(n,{\Bigl\lfloor \frac{p_n}{n} \Bigr\rfloor}\Bigr)=1$. Thus it suffices to show that if $n$ is prime, then $\gcd\Bigl(n,{\Bigl\lfloor \frac{p_n}{n} \Bigr\rfloor}\Bigr)=1$. – rogerl Apr 1 at 11:50
• Sure thanks. is there some kind of identity that enables us to express the greatest common divisor of three quantities in terms of products of the combinations of pairs that can be made from the three? ie $\gcd(a,b,c)$ in terms of $\gcd(a,b)$,$\gcd(b,c)$ &$\gcd(a,c)$? – Adam Apr 1 at 12:14
• with regards to proof for the second I was thinking – Adam Apr 1 at 12:17
• because I can see what you mean, by the first implying the second, I just want to perhaps use some kind of identity involving the second to establish more concise conditions for when some of the combinatoric pairs from it are not coprime and are coprime – Adam Apr 1 at 12:23
• $\gcd(n,\lfloor\frac{p_n}{n}\rfloor)=1$ if $n$ is prime because $p_n \lt n^2$ for $n\gt 1$. – FredH Apr 1 at 13:20