Introduction to Number Theory

Number Theory is a branch of pure mathematics devoted primarily to the study of integers and integers valued functions.


Application of Number theory:
  • Cryptography (ie. encryption and decryption )
  • Numerical Analysis
Things we will be discussing here.
  • Modular Arithmetic
Modular Arithmetic
  • Addition
    • (a+b) % m = (a%m +b%m) %m
      • Example:
        • Let a=5, b=7, and m=4
        • Simplifying LHS: (a+b)%m = (5+7)%4 = 12%4 = 0
        • Simplifying RHS: (a%m + b%m) %m = (5%4 + 7%4) % 4 = (1 + 3)%4 = 0
        • LHS=RHS
  • Subtration
    • (a-b) % m = (a%m -b%m) %m
      • Example:
        • Let a=5, b=7, and m=4
        • Simplifying LHS: (a-b)%m = (5-7)%4 = -2%4 = -2
        • Simplifying RHS: (a%m - b%m) %m = (5%4 - 7%4) % 4 = (1 - 3)%4 = -2
        • LHS=RHS
      • Later we will be discussing congruence where we will see that -2%4 is equivalent to 2%4.
  • Multiplication
    • (a*b) % m = (a%m *b%m) %m
      • Example:
        • Let a=5, b=7, and m=4
        • Simplifying LHS: (a*b)%m = (5*7)%4 = 35%4 = 3
        • Simplifying RHS: (a%m * b%m) %m = (5%4 * 7%4) % 4 = (1 * 3)%4 = 3
        • LHS=RHS
  • Division
    • (a/b) % m ≠ (a%m / b%m) %m
      • Example:
        • Let a=5, b=7, and m=4
        • Simplifying LHS: (a/b)%m = (5/7)%4 = 5/7
        • Simplifying RHS: (a%m / b%m) %m = (5%4 / 7%4) % 4 = (1 / 3)%4 = 1/3
        • LHS≠RHS
When these properties are used?
  • When a,b are in range of 10e18. As in our computer, we don't have any data structure which can store number larger than 64bit integer.
    • i.e. when Integer Overflow will occur.
  • Hashing Algorithms to encrypt the Messages or Password.
If you find any error or have some advice then feel free to comment.
In the next article, we will be discussing Modular Exponentiation.

Thank You

Comments