Background

Euclids algorithm might be one of the oldest to be recorded; however, it is used extensively in modern times, cryptography and internet security are paramount examples. Nonetheless, to get to this level of sophistication we need some mathematical tools.

Theorem (Extended Euclids algorithm) Let a and b be nonzero integers and d their greatest common divisor, then there are two integers x and y such that

ax + by = d.

This equation is known as Bezouts identity.

Assignment

Write a java program that given two nonzero integers a and b, computes integers x and y that satisfy Bezouts identity. Hint. Keep track of remainders in the standard Euclidean algorithm.

Example

Set a = 7 and b = 13 (to balance good and bad fortune :P), following Euclids algorithm we get: 13 = 1 7 + 6 7 = 1 6 + 1 6 = 6 1 + 0

This says that g.c.d(7, 13) = 1, and at the same time we can see that

1 = 7 1 6

= 7 1 (13 1 7)

= 7 13 + 7

= 7 2 + 13 (1)

it follows that x = 2 and y = 1.

Reminder

We encourage discussion and support among students, but sharing code or copying someone else work is unacceptable, violators will receive 0 for their lab grade. This issue is especially sensitive in this lab, since much work on the algorithm discussed already exists. In other words, do your own work.