Dtyjlui

I am not an expert on modulus arithmetic and I am computer scientist looking to see if there is a better way to solve an equation in the form of

$$(x^2 + 43) mod (44-2x)=0$$

I am currently doing a linear search, I have other equations I am trying to solve other equations that are similar, but the search is becoming inefficient for large values. Any help would be appreciated.

The solutions to this equations are

$$x = -9,5,21,23$$

I assume that you're looking to solve the equation over the integers.

First notice that when $x$ is even, then $x^2+43$ is odd, but the modulus is even. (The modulus is always even.) Therefore in order for $x$ to be a solution, $x$ must be odd. Let $x=2k+1$ then, for some integer $k$. Let's see if that simplifies things.

We now have
$$4k^2+4k+44 equiv 0 pmod{2(2k-21)}.$$

Cancelling a $2$ from the equation and the modulus at the same time, we now have
$$2k^2+2k+22 equiv 0 pmod{2k-21},$$
which is much nicer.

The reason it's much nicer is that $2k-21$ has leading coefficient 2, which divides the leading coefficient of $2k^2+2k+22$. Thus, we can subtract the equation $(2k-21)k=2k^2-21kequiv 0$ to get
$$23k + 22 equiv 0 pmod{2k-21},$$
and now we can subtract $11(2k-21)= 22k-231equiv 0$
to get the equation
$$k+253equiv 0 pmod{2k-21}.$$

Now we rewrite this. We want to find for which $k$ there exist $q$ such that $k+253 = q(2k-21)$.

Rearranging, we have $(2q-1)k = 253+21q$

Thus, $k$ is a solution if and only if $k$ can be written as $frac{21q+253}{2q-1}=10+frac{q+263}{2q-1}$.

Thus we have reduced the question to figuring out when $frac{q+263}{2q-1}$ is an integer.

This is kind of a pain, so let's solve the much easier question of when it is an integer or a half integer, which we can solve by noting that in that case,
$$frac{2(q+263)}{2q-1}=frac{2q+526}{2q-1}=1+frac{527}{2q-1}$$ will be an integer. Thus $2q-1$ will be a factor of $527$.

Note that $527$ is odd, so that $527/(2q-1)$ will always be odd, so that the resulting integer will always be even. This means that no value of $q$ gave a half integer solution, so every possible value of $q$ gives a value of $x$.
The factors of 527 are $pm 1$,$pm 17$,$pm 31$, and $pm 527$,
corresponding to values for $q$ of $1,0,9,-8,16,-15$, $264$, and $-263$.

These give values of $k$ of $11,10,19,2,26,-5,274$, and $-253$.
Thus we get solutions for $x$ of $23,21,39,5,53,-9,549$, and $-505$.

Hint $, x!-!22mid x^2!+!43-(x!-!22)(x!+!22) = 527= 17cdot 31,$ so $,x, =, 22pm{1,17,31,527}$

For $x=21$, $44-2x=2$ and the residue of any even number is $0mod 2$.

$21^2+43$ is even.

Note that if

$$x^2 + 43 equiv 0 pmod{44 - 2x} tag{1}label{eq1}$$

then multiplying by $-2$ gives

$$-2x^2 - 86 equiv 0 pmod{44 - 2x} tag{2}label{eq2}$$

Also, dividing $44 - 2x$ into $-2x^2 - 86$ gives

$$-2x^2 - 86 = left(x + 22right) left(44 - 2xright) - 1054 tag{3}label{eq3}$$

Thus, your original equation can be simplified to just look for cases where

$$-1054 equiv 0 pmod{44 - 2x} tag{4}label{eq4}$$

As such, you only need to check cases where $44 - 2x$ is a factor of $1054 = 2 * 31 * 17$, in particular, $pm 1, pm 2, pm 31, pm 17, pm 62, pm 34, pm 527, pm 1054$. For each value $n$ among these factors, you can then solve for $x$ by using $x = 22 - frac{n}{2}$. As such, for integral values of $x$, the factor must be even, giving the results of $x = 21, 23, -9, 53, 5, 39, -505, 549$.

Also, if you wish to avoid using negative modulus values, then you need to have $44 - 2x gt 0$, so $x lt 22$, giving the results of just $x = -505, -9, 5, 21$.