# Solve $3619t = 133$ in $\mathbb Z_{4557}$

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

-

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}$..

-

$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$

-

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.

-

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.$$

-