Let $k, p, q$ be distinct primes. How to determine unique $n \in \{q, q + k, q + 2k, \ldots, q + (p - 1)k\}$ such that $\gcd(n, p) \gt 1$

Question

Given the distinct primes $k, p, q$, is there a formula or algorithm to obtain the unique $n \in \{q, q + k, q + 2k, \ldots, q + (p - 1)k\}$ such that $\gcd(n, p) \gt 1$?

Answer 1

you need $q+nk\equiv 0 \bmod p \iff nk\equiv -q \bmod p$, so you need $n\equiv-qk^{-1}\bmod p$.

Finding the inverse of $k\bmod p$ can be done in two ways I know of:

• Using the euclidean algorithm to write $1=sk+tp$
• Using fermat's theorem ,noticing $k^{-1}\equiv k^{p-2}\bmod p$