find some integer to make an expression an integer

Question

suppose K is a fixed integer, P is a fixed prime number, can we always find an integer n to make $\frac{np+1}{k}$ an integer?

Answer 1

So you need $np+1$ to be divisible by $k$, which means $np\equiv-1 \mod(k)$.

Now, if you let $N = -n$, we have $Np \equiv 1 \mod(k)$.

By Euler's Theorem, there exists a solution $N$ to this equation when $p$ and $k$ are relatively prime.

This solution $N$ is called the multiplicative modular inverse of $p$ modulo $k$.

So, as long as $k$ is not $p$, you have a solution.

Answer 2

You cannot do this when $k=p$.

Answer 3

Note $\,\exists x\!:\ k\mid px+1\iff \exists x,y\!:\ ky - px = 1\iff \gcd(k,p)=1,\,$ by Bezout

If so then $\,x \equiv -p^{-1}\pmod{\!k},\,$ which is computable by the Extended Euclidean algorithm, or by Gauss's algorithm. if $\,p\,$ or $\,k\,$ is prime.