Knödel numbers - Find Kn
Pyth, 29 28 bytes

.f&amp;tPZ!f&amp;q1iTZt%^T-ZQZSZvzhQ


1 byte saved thanks to Jakube and orlp.

Demonstration.

Input in the form

p
n


A fairly straightforward calculation. Relative primeness is checked via Pyth's gcd function. This code showcases .f, Pyth's "first n satisfying" function.

I have incorporated the implicit condition that m &gt; n by starting the search for m values at n + 1.