Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.