Finding Specific Solution to Linear Diophantine Equation

2017-12-03 03:03:03

Other than by brute force, how can I solve $a=20k+91806$ to find the solution $a=96646$ (or $k=242$) if I know the following:

A. The prime factorization of $91806$ is $2,3,11,13,107$.

B. $GCD(a,91806)=22$.

C. $a\equiv 91806 \mod 20$

Is it possible to find that specific solution with the known information using the Chinese Remainder Theorem or some similar process?

EDIT: I noticed that $k=242$ for the solution I want. $242 = 11(GCD)$. Does knowing that $GCD(a,91806)=22$ somehow allow me to iterate $k$ by $22$ instead of by $1$ or is this just a coincidence?

The condition $\mathrm{gcd}(a,91806) = 22$ (in particular, $22 | a$) implies that $k$ is a multiple of $11$.

To make the gcd exactly $22$, there are some further requirements on $k$; for example, $k$ must not be a multiple of $3$; but incrementing $k$ by $11$ will find solutions rather quickly.

For example, there is a smaller solution to your conditions with $k = 11$ and $a = 92026$.

  • The condition $\mathrm{gcd}(a,91806) = 22$ (in particular, $22 | a$) implies that $k$ is a multiple of $11$.

    To make the gcd exactly $22$, there are some further requirements on $k$; for example, $k$ must not be a multiple of $3$; but incrementing $k$ by $11$ will find solutions rather quickly.

    For example, there is a smaller solution to your conditions with $k = 11$ and $a = 92026$.

    2017-12-03 05:08:06