Skip to content

Instantly share code, notes, and snippets.

@iandioch

iandioch/modulus_rules.md

Last active February 13, 2016 04:13
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save iandioch/7246cde2c58d3aa38c22 to your computer and use it in GitHub Desktop.
Save iandioch/7246cde2c58d3aa38c22 to your computer and use it in GitHub Desktop.
Download ZIP
Arithmetic rules with modulus
Raw
modulus_rules.md

Addition

(a + b) % n = ((a % n) + (b % n)) % n

Multiplication

(a * b) % n = ((a % n) * (b % n)) % n

Division

(a / b) % n = ((a % n) * ((b ^(-1)) % n)) % n

Misc

(a % n) % n = a % n (identity)

(a * n) % n = 0 (as proven by multiplication above)

therefore (n!) % n = 0

More info in the wiki article

This article has some nice modulus tricks.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment