1
$\begingroup$

Solve for integers, $x, y$

$4258x+147y=369 \implies 4258x \equiv 369 \pmod{147}$

I got this question from SE, but I want to try this approach.

I suppose we will find the inverse modulus of $4258 \pmod{147}$ using Euclid's algorithm. So:

$4258 = 28(147) + 142$

$147 = 1(142) + 5$

$142 = 28(5) + 2$

$5 = 2(2) + 1 \implies 1 = 5 - 2(2)$

$$1 = 5 - 2\bigg( 142 - 28(5) \bigg) = 5 - 284 + 2(28(5))$$

$$= 5 - 284 + 2\bigg( 28\cdot (147 - 142) \bigg)$$

$$= 5 - 284 + 2\bigg( 28\cdot(147 - 4258 + 28(147)) \bigg)$$

I still dont understand this.

But I am lost in this algorithm, how should I compute further?

$\endgroup$

3 Answers 3

Reset to default
1
$\begingroup$

Note that you have got a spare $5$ at the end. It is easier to deal with the brackets as they arise line by line. You will see that each line has two terms

$$1=5-2\cdot (2)$$

Replace $2$

$$1=5-2\cdot (142-28\cdot 5)=-2\cdot(142)+57\cdot (5)$$

Replace $5$

$$1=-2\cdot(142)+57\cdot(147-1\cdot (142))=-59\cdot (142)+57\cdot(147)$$

Replace $142$

$$1=-59\cdot(4258-28\cdot147)+57\cdot(147)\equiv -59\cdot4258 \bmod 147$$

$\endgroup$
7
  • $\begingroup$ So what is the strategy? In the end you should have $m\cdot(x)$ where you are trying find the inverse of inverse of $n$ $\pmod{m}$? $\endgroup$
    – Amad27
    Jan 25, 2015 at 8:44
  • $\begingroup$ Note you get $-59\cdot 4258$ plus a multiple of $147$ - you don't have to calculate what this is, because you are only interested in the result modulo $147$. The inverse you are looking for is $-59$ $\endgroup$
    – Mark Bennet
    Jan 25, 2015 at 8:46
  • $\begingroup$ Wait, we have: $1 = -59(4258 - 28\cdot 147) + 57(147)$ So with multiplies of $147$ we get: $-1652(147) + 57(147) = 147(-1605) \equiv 135$ I dont get the same as you. (FROm the LAST line). $\endgroup$
    – Amad27
    Jan 25, 2015 at 8:50
  • $\begingroup$ @Amad27 Modulo $147$ we have that $147 \times$ anything $\equiv 0$. So I've just left the multiples of $147$ out, rather than do extra work. To solve your original question, multiply by $-59$ and reduce modulo $147$. $\endgroup$
    – Mark Bennet
    Jan 25, 2015 at 8:55
  • $\begingroup$ I dont see one thing here though. How is $-59$ the inverse by not $57$? Because in the last line you also have a factor $57\cdot (147)$? $\endgroup$
    – Amad27
    Jan 25, 2015 at 8:59
1
$\begingroup$

The Extended Euclidean Algorithm does just what you want. It keeps track of the forward and backward substitutions. There is an implementation explained in this answer. Here is how it can be used to solve this equation: $$ \begin{array}{r} &&28&1&28&2&2\\\hline 1&0&1&-1&29&-59&147\\ 0&1&-28&29&-840&1709&-4258\\ 4258&147&142&5&2&1&0\\ \end{array}\quad \begin{array}{l} \\ \text{this row times }4258\\ \text{this row times }147\\ \text{their sum is this row}\\ \end{array} $$ Because we each column is a linear combination of the two previous columns, the top row time $4258$ plus the middle row times $147$ equals the bottom row.

Thus, we have $$ 4258(-59+147k)+147(1709-4258k)=1 $$ Multiply the particular solution by $369$ to get $$ 4258(-21771+147k)+147(630621-4258k)=369 $$ Choose $k$ to get another particular solution. For example, $k=149$ gives $$ 4258(132)+147(-3821)=369 $$

Here is the algorithm unrolled to track the $\color{#00A000}{4258}$ and $\color{#C000FF}{147}$: $$ \begin{align} 142&=\color{#00A000}{4258}-28\cdot\color{#C000FF}{147}\\ 5&=\color{#C000FF}{147}-1\cdot(\overbrace{\color{#00A000}{4258}-28\cdot\color{#C000FF}{147}}^{142})=29\cdot\color{#C000FF}{147}-1\cdot\color{#00A000}{4258}\\ 2&=(\overbrace{\color{#00A000}{4258}-28\cdot\color{#C000FF}{147}}^{142})-28\cdot(\overbrace{29\cdot\color{#C000FF}{147}-1\cdot\color{#00A000}{4258}}^5)=29\cdot\color{#00A000}{4258}-840\cdot\color{#C000FF}{147}\\ 1&=(\overbrace{29\cdot\color{#C000FF}{147}-1\cdot\color{#00A000}{4258}}^5)-2\cdot(\overbrace{29\cdot\color{#00A000}{4258}-840\cdot\color{#C000FF}{147}}^2)=1709\cdot\color{#C000FF}{147}-59\cdot\color{#00A000}{4258} \end{align} $$

$\endgroup$
2
  • $\begingroup$ (+1) But how can I do this using: $$= 5 - 284 + 2\bigg( 28\cdot(147 - 4258 + 28(147)) \bigg)$$ $$= 5 - 284 + 2\bigg( 28\cdot 147 - 28\cdot 4258 + 28^2\cdot 147 \bigg)$$ $$1 \equiv -279 - 56\cdot 4258$$ But this isnt correct? I took out the $147n$ terms because $\pmod{147}$ results that in $0$? $\endgroup$
    – Amad27
    Jan 25, 2015 at 10:25
  • $\begingroup$ @Amad27: I have added an unrolled version of the algorithm. Perhaps it is closer to what you want. $\endgroup$
    – robjohn ♦
    Jan 25, 2015 at 13:52
0
$\begingroup$

The purpose of reverse substitution is to express $1=ar_1+br_2$ where $r_1,r_2$ are some consecutive remainders obtained in the algorithm.

So you need to combine the terms having $5$ after the second step, like so:

$1 = 5 - 2(142 - 28(5)) = 57(5)-2(142)$.

  • $= 57(147 - 1(142)) - 2(142) = 57(147)-59(142)$.

Also, I have corrected your mistake: $18\to 28$.

Once you express $1=a(147)+b(4258)$, where $a,b$ are integers, take modulo $147$ on both sides, and you will get $b(4258)\equiv 1\quad(\text{mod }147)$. So $b$ is the inverse of $4258$ modulo $147$. In the original equation, $x\equiv b(4258)x\equiv b(369)\quad(\text{mod }147)$.

To see why, $x=(a\times 147+b\times 4258)\times x$

  • $=b\times 4258x+ax\times 147=b\times 369+c\times 147+ax\times 147$
  • $=b\times 369+(c+ax)\times 147$
$\endgroup$
7
  • $\begingroup$ So what is the inverse? Mark Bennet said it was (-59) but here I think you are doing something different? $\endgroup$
    – Amad27
    Jan 25, 2015 at 9:00
  • $\begingroup$ @Amad27 I didn't want to give you all the working. The idea is the most important. $\endgroup$
    – user1537366
    Jan 25, 2015 at 9:06
  • $\begingroup$ I dont understand the idea. which is why I asked which one here is the inverse modulus? $\endgroup$
    – Amad27
    Jan 25, 2015 at 9:08
  • $\begingroup$ @Amad27 See my edits. $\endgroup$
    – user1537366
    Jan 25, 2015 at 9:14
  • $\begingroup$ I would appreciate it, if you could keep it simple? I am new to this? please see my edits (to the question) and try to comply? $\endgroup$
    – Amad27
    Jan 25, 2015 at 9:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .