# Extended Euclidean algorithm and modular multiplicative inverse element

After my first exercise here is another. Again, this is exactly that: Exercise, which means that the output doesn't necessarily need to be beautifully formatted, etc. I probably have some variable naming issues around and also more general issues.

# coding=utf-8

"""Basic usage:
\$ python xggt.py 3343 77
(1, -12, 521)
65
"""

import argparse

###############################################################################

def main():
"""Prints out the results of xggt().
xggt() takes two non-optional integers as arguments.
"""

parser = argparse.ArgumentParser()
args = parser.parse_args()

if (args.num_1 == 0) and (args.num_2 == 0):
else:
print(xggt(args.num_1, args.num_2))
print(modinv(args.num_1, args.num_2))

###############################################################################

def xggt(num_1, num_2):
"""Implements the Extended Euclidean algorithm.
Returns the greatest common divisor of two integers > 0.
Also returns the coefficients of Bézout’s identity.
"""

if num_1 % num_2 == 0:
return(num_2, 0, 1)
else:
gcd, lin_fact_1, lin_fact_2 = xggt(num_2, num_1 % num_2)

lin_fact_1 = lin_fact_1 - num_1 // num_2 * lin_fact_2

return(gcd, lin_fact_2, lin_fact_1)

###############################################################################

def modinv(num_1, num_2):
"""Returns the modular multiplicative inverse of two integers > 0
"""

gcd, lin_fact_1, _ = xggt(num_1, num_2)

if gcd != 1:
return None
else:
return lin_fact_1 % num_2

###############################################################################

if __name__ == '__main__':
main()

• The egcd function (alias xggt) is nice and tight. I like it, but my head spins trying to match it against the math... Perhaps it would be easier to see the elegance of it if you used shorter names (single letters, corresponding to the letters u, v, s, r used in the formulas). – DarthGizka Nov 16 '14 at 9:00
• I'd lose the else in xggt, though. It is confusing because it's superfluous. – DarthGizka Nov 16 '14 at 9:07
• @DarthGizka Variable naming was my biggest concern, too. Also thank you for pointing out the unnecessary else. – kleinfreund Nov 16 '14 at 9:41
• @kleinfreund: There seem to be some (copy/paste?) errors in your program, it does not run: 1) parser is undefined in main() 2) lin_fact_2 is undefined in xggt(). The first error is easy to fix, but the second makes it difficult to understand your algorithm. – Martin R Nov 16 '14 at 9:47
• @kleinfreund: I assume it should be gcd, lin_fact_1, lin_fact_2 = xggt(num_2, num_1 % num_2) in xggt(). – Martin R Nov 16 '14 at 9:58

This looks like a bug in the input validation:

if (args.num_1 == 0) and (args.num_2 == 0):
else:
print(xggt(args.num_1, args.num_2))
print(modinv(args.num_1, args.num_2))


The message "Please enter two positive integers." contradicts with the condition: if both numbers are 0. I think you meant more like this:

if args.num_1 > 0 and args.num_2 > 0:
print(xggt(args.num_1, args.num_2))
print(modinv(args.num_1, args.num_2))
else:


I also removed redundant parentheses.

You had redundant parentheses in other places too:

    return(num_2, 0, 1)
# ...
return(gcd, lin_fact_2, lin_fact_1)


These are all unnecessary, so I recommend to remove them.

You can simplify x = x - ... with x -= ..., for example here:

# instead of this:
# lin_fact_1 = lin_fact_1 - num_1 // num_2 * lin_fact_2
lin_fact_1 -= num_1 // num_2 * lin_fact_2


Other than these minor issues, I think this is good and clean code! The names seem quite fine to me.

Some general feedback:

• Take a look at PEP8 and check your code with http://pep8online.com/
• Don't write those ######### lines, because PEP8 says:

Separate top-level function and class definitions with two blank lines.

• If you add #!/usr/bin/env python in the first line, people can directly execute your code (on Linux machines at least). This is called Shebang. See my article for a very short explanation.

• ArgumentParser(description=__doc__) is very nice.
• Do you know doctests? I think they are very neat if you have simple functions that have parameters of integers and output of integers.
• The code follows PEP8. I use it from the command line. What's wrong with the separation lines? Could you elaborate on what the #!... python does exactly for Linux users, please? Also, I looked at doctests and I use them now. Thank you. – kleinfreund Nov 16 '14 at 12:05
• @kleinfreund: I've extended my answer a little bit. What is wrong with separation lines? Well, it is not commonly used. We (the community of Python developers) have PEP8 to make code look similar, even if many different people write it. If it looks familiar, it is easier to read. In Python, top level functions should get separated by two blank lines. Not by #### lines. – Martin Thoma Nov 16 '14 at 12:11