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.

What I understand:

This question asks to solve for $t$ such that when $(3619 \times t)$ is divided by $4557$ the remainder is $133$

I have found a Bezout identity
$7 = 34 \times 3619 - 27 \times 4557$ and
$1 = 34 \times 517 - 27 \times 651$ and

and I see that $133 = 7 \times 19$ so
$133 = 646 \times 3619 - 513 \times 4557$

Somehow we are supposed to arrive at $t \equiv 646 \pmod{651}$ and I feel like I've worked out all the bits and pieces but having trouble putting it together

share|improve this question

4 Answers 4

up vote 3 down vote accepted

Start it over, on a new, clear page.

So, what we have is that $7$ is the greatest common divisor: $3619=7\cdot 517$, $4557=7\cdot 651$, and $133=7\cdot 19$, so it reduces to $$517t\equiv 19 \pmod{651}$$ then, I would use $517\equiv -134 \pmod{651}$..

share|improve this answer

$4557=3 \cdot 49 \cdot 31$. Your equation is equivalent to $$x \equiv 1 \ \ (3)$$ $$42 x \equiv 35 \ \ (49) $$ $$23 x \equiv 9 \ \ (31) $$

or equivalently

$$x \equiv 1 \ \ (3)$$ $$6 x \equiv 5 \ \ (7) $$ $$ x \equiv 26 \ \ (31) $$

You can actually solve the second equation to get $x \equiv 9 \ \ (7)$.

Then use the Chinese remainder theorem to solve. The answer is $1948$

share|improve this answer

Take your equation $7=34 \times 3619-27 \times 4557$ and multiply by 19. You'll get $$133 = (34*19) \times 3619 - (27*19) \times 4557.$$ That is, $133=646*3619-513*4557$. In $Z_{4557}$ the subtracted term is 0, so you have your desired $3619*(646)=133$ in $Z_{4557}$.

So it looks like you were on the right track.

share|improve this answer

If $a b = a c \pmod{n}$, then $b = c \pmod{\dfrac{n}{(a,n)}}$. In this case, the common factor is $7$ and $(7, 4557) = 7$, so $7 \cdot 517 x = 7 \cdot 19 \pmod{\dfrac{4557}{(4557, 7)}}$ gives $517 x = 19 \pmod{651}$. The Extended Euclidean algorithm gives

$$34 \cdot 517 + (-27) \cdot 651 = 1.$$

$$\matrix{ 651 & & 34 \cr 517 & 1 & 27 \cr 134 & 3 & 7 \cr 115 & 1 & 6 \cr 19 & 6 & 1 \cr 1 & 19 & 0 \cr}$$

Reducing mod $651$ gives $34 \cdot 517 = 1$, so $517^{-1} = 34 \pmod{651}$. So multiplying the last equation by $34$ gives $x = 646 \pmod{651}$.

However, the original equation was a congruence mod $4557$. Therefore, there will be $7$ solutions mod $4557$. You can obtain the others by adding multiples of $651$ to $646$: $$646, \quad 1297, \quad 1948, \quad 2599, \quad 3250, \quad 3901, \quad 4552.$$

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.