0
$\begingroup$

Not sure if these are relevant but the previous questions asks:

  • Find $gcd(7429, 4991)$ Worked out to be $23$
  • Express 4991 as product of primes: $23 * 7 * 31$
  • Find all integer solutions for $7429x + 4991y = 460$ which I have found to be
    $x = 860 - 217t$
    $y = -1280 + 323t$

And the final answer given by the provided solution is $23$ which of course happens to be $gcd(7429,4991)$ and I feel like this is no coincidence

I feel like I've worked out the bits and pieces to do the question but I don't know how to put it together

1 Answers 1

2

Let's consider the general picture a bit before trying to solve this specific case: How many solutions $0 \le t < n$ are there of $at \equiv b \pmod {m}$?

Factor $a = uv$ into a part $u$ invertible $\pmod m$ and $v|m$. Then we are interested in solving $vt \equiv b' \pmod {m}$ where $b' \equiv u^{-1}b \pmod m$.

If $v=1$ we simply have $1$ or $0$ solutions depending on whether $b'$ lies in the range. Otherwise we'd need $b'$ to be a multiple of $v$ for there to be any solutions at all (you can prove this by contradiction).

Suppose there were two solutions $t$ and $t'$ then $a(t'-t) \equiv 0 \pmod {m}$, in other words if we found some minimal solution $t$, then every other solution would be of the form $t+d$ for some $ad|m$.


So to compute the solutions in this case let's start by computing $\gcd(4991,7429) = 23$ so $4991 = 217 \cdot 23$ and $217^{-1} \equiv 582 \pmod {7429}$ so we should start by finding the smallest $t$ satisfying $23 t \equiv 582 \cdot 460 \equiv 276 \equiv 23 \cdot 12 \pmod {7429}$, which is a multiple of $23$ so we're in luck and $t=12$ is the smallest solution.

Now we can just go through the divisors of $7429/23 = 323 = 17 \cdot 19$ in order:

12+17=31 12+19=49 12+17*19=335 

all are within the specified range so we have $4$ solutions.