Question

Please, check my stuff, I don't know what is wrong!!
Find all solutions of 102x +1001 y = 1

Answer 1

Sure

Answer 2

So, did you learn about the "zero's" of an equation yet or no??

Answer 3

1001 = (8) 120 + 41, right?

Answer 4

Hence 41 = 1001 -(8) 120

Answer 5

120 = (2)41 +38 , hence 38 = 120 - (2)41

Answer 6

41 = 38 + 3 , hence 3 = 41 -38
and 38 = (12)3 +2 , hence 2 = 38 -(12)3
3 = 2+ 1
1 = 3-2

Answer 7

Am I right so far?

Answer 8

Now, backward
1 = 3-2 = 3 -(38 -(12)3 ) = (13)3 -38

Answer 9

For the equation 102x + 1001y = 1, you know that the gcd of 102 and 1001 is 1.
Therefore, there is some linear combination of 102 and 1001 that adds to 1.
Use the Euclidean Algorithm to find the coefficients m, n so that
102 n + 1001 m = 1.
Once you find that m and n, note that you can generate an infinite set of solutions by noting:
102 (n + 1001) + 1001 (m - 102) = 1 is always a true statement
if n and m is a solution to 102 n + 1001 m = 1.

Also, 102 (n + 2*1001) + 1001 (m - 2*102) = 1 is true.
102 (n + 1001k) + 1001 (m - 102)k = 1 for any integer k is true as well.

So we have an infinite set of solutions based on our initial solution given by the Euclidean algorithm to find the gcd of two numbers.

Answer 10

@Loser66

Answer 11

I need a concrete solution, i.e. numbers in answer, not m, k, or n

Answer 12

and I am on the way, just don't know where I messed up. So that I need someone check my steps

Answer 13

1= (13) 3 -38 = (13 )(41-38) -38 = (13) 41 -(14)38
1= (13) 41 -(14) (120 -(2)41) = (13)41 -(14)120 +(28) 41= (41) 41 -(14)120

Answer 14

1= (41)(1001-(8)`120)-(14)120 = (41) 1001-(328)120 -(14)120 = (41) 1001 -(342) 120

Answer 15

ok, so far so good.
Hence x = 41 and y = -342, and that is only one solution, right?

Answer 16

oh, no, still have other. Since gcd (1001,120) = 1, and 1|1, hence the solutions should be
\(X = x + 1001t \rightarrow X = 41 + 1001 t\)

and \(Y= y - 102 t \rightarrow Y = -342 -102 t\) for all t in \(\mathbb Z\)

Answer 17

But I don't know where I messed up. I don't get the correct one.

Answer 18

I mean, if t = 1, then X = 41 + 1001 = 1042
Y = -342 -102 = -444
Plug back to original one.
102 X +1001Y = 102 (1042) + 1001(-444) = 106284-444444=-338160
while I am supposed to get 1 back!!!

Answer 19

is that a linear diophantine eqn ?

Answer 20

Yes, it is @ganeshie8

Answer 21

what is your one particular solution ?

Answer 22

oh, I see where I messed up, at the very first step 1001 = (9)102 +83

Answer 23

Not 8(120) +41 OMG

Answer 24

@ganeshie8 Let me post my first try with it, and still get the wrong answer :(

Answer 25

Yes

Answer 26

Forward :
```
1001 - (102 x 9) = 83
102 - (83 x 1) = 19
83 - (19 x 4) = 7
19 - (7 x 2) = 5
7 - (5 x 1) = 2
5 - (2 x 2) = 1
```

Answer 27

Ok, got this. I follow you,

Answer 28

next, please

Answer 29

Next, start from last step

Answer 30

your goal is to express `gcd` as a linear combination of 1001 and 102

Answer 31

Yes, I know

Answer 32

Forward :
```
1001 - (102 x 9) = 83
102 - (83 x 1) = 19
83 - (19 x 4) = 7
19 - (7 x 2) = 5
7 - (5 x 1) = 2
5 - (2 x 2) = 1
```

Backward :
```
1 = 5 - 2*2
= 5 - 2(7-5*1) = 5(1+2) + 7(-2) = 5(3) + 7(-2)
```

Answer 33

fine with that step ?

Answer 34

i got (422)102 -(43) 1001 =1 . Finally!!

Answer 35

Hence \(x_0 = 422; y_0 = -43\) right?

Answer 36

good, so (422, -43) is one particular solution to the eqn 102x + 1001y = 1

Answer 37

next find the null solution

Answer 38

What is null solution? I know general solution only
That is \(X = x_0 + 1001 t\) and \(Y= y_0 - 102 t\)

Answer 39

t*(1001, -102) is called the null solution

Answer 40

particular solution : (422, -43)
null solution : t*(1001, -102)

complete solution = particular + null = (422, -43) + t*(1001, -102)

Answer 41

if you see, the points `t*(1001, -102)` are the solutions to the equaiton 102x + 1001y = 0. thats the reason it is called a null solution

Answer 42

Yes, I saw it. Thank you so much. It is not hard, right? just easy make mistake and it drove me crazy when I can't find where the mistake is. :(

Answer 43

it's not hard as it is a very familairnew pattern,
you must have seen this kind of constructing solutions in linear algebra and differential equations

Answer 44

you find any one solution,
find the null solution (this is almost always trivial)

write out the complete solution

Answer 45

Yes. Thank you very much

Answer 46

Here's a slightly different way to do it. It's basically the extended euclidean algorithm, but for me, it helps to have variables thrown in


1001 = 9*102 + 83 -----> 83 = 1001 - 9*102
102 = 1*83 + 19 -----> 19 = 102 - 1*83
83 = 4*19 + 7 -----> 7 = 83 - 4*19
19 = 2*7 + 5 -----> 5 = 19 - 2*7
7 = 1*5 + 2 -----> 2 = 7 - 1*5
5 = 2*2 + 1 -----> 1 = 5 - 2*2



let x = 1001 and y = 102


83 = 1001 - 9*102
83 = x - 9*y
------------------
19 = 102 - 1*83
19 = y - 1*(x - 9*y)
19 = 10y - x
------------------
7 = 83 - 4*19
7 = (x - 9*y) - 4*(10y - x)
7 = 5x-49y
-------------------
5 = 19 - 2*7
5 = (10y - x) - 2*(5x-49y)
5 = 108y-11x
-------------------
2 = 7 - 1*5
2 = (5x-49y) - 1*(108y-11x)
2 = 16x-157y
-------------------
1 = 5 - 2*2
1 = (108y-11x) - 2*(16x-157y)
1 = 422y-43x


-43x + 422y = 1
-43(1001) + 422(102) = 1
1001*(-43) + 102*(422) = 1

Answer 47

or you can use the method described here

https://en.wikibooks.org/wiki/Discrete_Mathematics/Number_theory#The_extended_Euclidean_algorithm

to generate this table

\[
\begin{array}{ccccc}
i & q & r & u & v\\
-1 & X & 1001 & 0 & 1\\
0 & X & 102 & 1 & 0\\
1 & 9 & 83 & -9 & 1\\
2 & 1 & 19 & 10 & -1\\
3 & 4 & 7 & -49 & 5\\
4 & 2 & 5 & 108 & -11\\
5 & 1 & 2 & -157 & 16\\
6 & 2 & 1 & \color{red}{422} & \color{red}{-43}\\
7 & 2 & 0 & X & X\\
\end{array}
\]

102u + 1001v = 1
102(422) + 1001(-43) = 1