1
$\begingroup$

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

4 Answers 4

3

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

2

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

1

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.

1

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