# Solving congruences/modular inverses with a polynomial modulus

After going through easily a couple dozen answers here (in particular by @BillDubuque) and articles elsewhere, I'm still stumped something that seems like it ought to be simple. First, here's the setup; all variables are non-zero integers.

Lemma: Given $$(a,b) = 1$$ and $$(a, c,d)=1$$, and $$a > b \geq 1$$:

$$\left\{ \begin{array}{lr} u = ax + bc \\ v = ay + bd \\ \end{array} \right\} \iff \left(u \mid v \iff y \equiv c'dx \pmod u \right)$$

where $$c'$$ is the modular inverse of $$c$$ in modulus $$u$$, because I hate typing the exponent every time.

Proof (Sketch): The required coprimes ensure all our variables have unique modular inverses. Thus, starting with $$u = ax + bc \equiv 0 \pmod u$$, and continuing in the same modulus:

$$ax \equiv -bc \iff adx \equiv -bcd \\ u \mid v \iff u \equiv v \equiv 0 \iff ay \equiv -bd \iff acy \equiv -bcd \\ acy \equiv adx \iff cy \equiv dx \iff y \equiv c'dx$$

This was discussed some in a simpler form in this post and its answers.

This has been useful in analyzing sequences like this, in particular examining which primes divide the numbers generated by each entry. But I've run up against a bit of a wall with modular inverses in a variable modulus.

Let $$a=15, b=1, c=-7, d=2$$. In addition, $$x>0$$ is even and $$u$$ is prime. (This formulation asks: What primes of the form $$15k-7$$ (with $$k$$ even), e.g. $$[23, 53, 83, \dots]$$ divide numbers of the form $$15n +2$$ (with $$n$$ odd), e.g. $$[17, 47, 77, \dots]$$?)

To find $$y = c'dx$$, we need to solve for $$c'$$, giving the equation

$$-7c' \equiv 1 \pmod{15x-7}$$

and $$c'$$ should be a function of $$x$$. And I can't find a way to do it. I know the solution but I don't know how to show the process of getting to that solution. Extended Euclidean algorithm, polynomial long division, throwing things into Sage to see what comes out... either I get no solution, conflicting values, or infinite loops.

The solution (or one form of it), determined empirically (it's not hard to force a computer to calculate a few hundred thousand inverses), is $$c' \equiv 2-x' \pmod {15x-7}$$.

But I can't prove it, or show where it came from. Is the problem that there are some values of $$x$$ (i.e., $$x = 7k$$) for which there is no answer, therefore no general solution exists that one can readily solve? Does anyone have thoughts on how to solve what I feel like should be a simple modular inverse?

Edit to add: an example of a congruence similar to this that is solvable is $$2a \equiv 1 \pmod {2x+1}$$, for which the solution is $$a \equiv x+1$$. $$2$$ has a modular inverse in any odd modulus. Similarly, $$x$$ is its own inverse mod $$x+1$$. Is there a method of determining when these problems have solutions, and when they don't? Is it merely a matter of "if it's possible for the integer or polynomial you're trying to invert to not be coprime to the modulus, it can't be solved"?

• $\!\bmod p=\color{#c00}{30k-7}\!:\,\ 0\equiv 17+30n\!\!\!\overset{\times\ k\!}\iff\! 0\equiv 17k+\color{#c00}{30k}n\equiv 17k+\color{#c00}7n\iff n/k\equiv -17/7\$ (or, using fractions: $\ \color{#c00}{7/k}\equiv 30\equiv -17/n\,)\qquad$ May 30 at 10:45
• e.g. $\,k\!=\!1\!:\, \bmod p\!=\!23\!:\ n\equiv \dfrac{-17}7\equiv \dfrac{6}7\equiv \dfrac{18}{21}\equiv \dfrac{18}{-2}\equiv -9\equiv \color{#0a0}{14},\,$ and $\,17\!+\!30(\color{#0a0}{14}) = 23(19)\qquad$ May 30 at 10:46
• Generally $\ 19(30k-7) = 30(19k-5)+17\,$ by $\,n\equiv \dfrac{-17}{30}\equiv\dfrac{19(\color{#c00}7)-5(30)}{\color{#c00}{30}}\equiv 19\color{#c00}k-5\qquad$ May 30 at 11:53
• @BillDubuque, do you feel the problem lies in using mod $15x \pm b$ rather than the (maybe more natural?) $30x \pm b$? I ask because I was hoping for a more general solution--solving individual cases is quite easy. I'd still like to find an expression in $x$, i.e., $c' \equiv f(x)$, of the sort I mentioned in the edits. May 31 at 0:06
• $N$ odd $\Rightarrow N = 2n+1\,$ so $\,15N+2 = 15(2n+1)+2 = 30n+17\,$ so your example is equivalent to asking when a prime $\,p = 30k-7\,$ divides $\,30n+17,\,$ i.e. when $\, 30n+17\equiv 0\pmod{\!p},\,$ which is what I begin with in my first comment. Please give an example of the more general problem that you cannot solve the above way. May 31 at 21:37

If $$\,\rm\color{#90f}{prime}$$ $$\,ax\!+\!c\mid ay\!+\!d\,$$ then $$\,\color{#90f}{(a,c)=1}\,$$ (except degenerate cases), thus by $$\rm\color{#c00}{Bezout}$$
$$(a,c)=1\Rightarrow \exists\, j,k\!:\ \color{#c00}{ja\!-\!kc=-d},\,\ {\rm so}\, \bmod ax\!+\!c\!:\,\ y \equiv \dfrac{\color{#c00}{-d}}a\equiv \dfrac{\color{#c00}{ja\! - \!kc}}a \equiv \bbox[5px,border:1px solid #c00]{j + k x}\qquad$$
Explicitly: $$\,\ {(ax\!+\!\color{#c00}c)\color{#c00}k = \color{#c00}a(kx\!+\!\color{#c00}j)\color{#c00}{+d}}$$
e.g. your $$\,15x\!-\!7\mid 15y\!+\!2\,$$ has $$\,ja\!-\!jc = -d\,$$ $$\leadsto \,15j\!+\!7k = -2,\,$$ so $$\!{\bmod 7\!:\ j \equiv -2},\,$$ so $$\,\color{#0a0}{j = -2\!+\!7m},\,$$ so $$\,k = (-2\!-\!15\:\!\color{#0a0}j)/7 = (-2\!-\!15(\color{#0a0}{-2\!+\!7m)})/7 = 4-15m,\,$$ so $$\,j+kx \equiv -2\!+\!4x +(7\!-\!15x)m,\,$$ which agrees with your sought solution for $$\,m=0$$.
Note $$\,(a,ax\!+\!c)\! =\! (a,c)\!=\!1\,$$ so $$\bmod ax\!+\!c\!:\ a^{-1}$$ exists, so $$\,\frac{n}a := na^{-1}\,$$ uniquely exists too.