• Support PF! Buy your school textbooks, materials and every day products Here!

Extended euclid question ( )

  • Thread starter Bob19
  • Start date
  • #1
71
0
extended euclid question (URGENT!!!!)

Hi
Having the following linear combination of the two divisors a = 403 and b = 3263
403x + 3263y = 26
gcd(a,b) = 13
Using the extended euclid I get
3263 = 8*403 + 39 (1)
403 = 10 * 39 + 13 (2)
39 = 13 * 3
therefore gcd(a,b) = 13
Then using extended euclid to find x,y
I rewrite (1) and (2)
13 = 403 - 10 * 39 (z)
39 = 3263 - 8*403 (t)
According to ex.euclid I insert t into z and get the following:
13 = 403 - 10 * 3263 + 80 * 403

My question is how do I from this result derive x,y ???

Sincerley and God bless You all.

/Bob
 

Answers and Replies

  • #2
shmoe
Science Advisor
Homework Helper
1,992
1
You're very close. Use
Bob19 said:
13 = 403 - 10 * 3263 + 80 * 403
to write 13 as a linear combination of 403 and 3263. Then compare with your desired 403x + 3263y = 26 equation.
 
  • #3
71
0
Thank You for Your answer,

What do You mean ?

13 = 403 - 10 * 3263 + 80 * 403 can be divided by 13, but how does this allow be to find x,y ??

/Bob

shmoe said:
You're very close. Use
to write 13 as a linear combination of 403 and 3263. Then compare with your desired 403x + 3263y = 26 equation.
 
Last edited:
  • #4
Fermat
Homework Helper
872
1
your original eqn is,

403x + 3263y = 26

or,

26 = 403x + 3263y

and you have,

13 = 403 - 10 * 3263 + 80 * 403 = 403*81 - 10*3263

or,

26 = 403*162 - 3263*20

Looking at the bolded lines, can you now see what the solutions for x and y are ?
 

Related Threads on Extended euclid question ( )

  • Last Post
Replies
6
Views
332
Replies
4
Views
3K
Replies
2
Views
1K
Replies
0
Views
3K
Replies
5
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
3
Views
10K
  • Last Post
Replies
2
Views
2K
Replies
1
Views
2K
Replies
2
Views
1K
Top