# Slight Introduction to Number Theory

• A prime number is an integer that can only be divided without remainder by positive and negative values of itself and 1. Prime numbers play a critical role both in number theory and in cryptography.
• Discrete logarithms are fundamental to a number of public-key algorithms. Discrete logarithms are analogous to ordinary logarithms, but operate over modular arithmetic.
• 1 is not considered as prime number.

Prime Numbers

• Fundamental Theorem of Arithmetic:
• Any integer a > 1 can be factorized in a unique way as: .
• Where p1 < p2 < … < pt are prime numbers and where each is a positive integer.
• The value of any given positive integer can be specified by simply listing all the nonzero exponents in the foregoing formulation: The integer 12 is represented by {a2 = 2, a3 = 1}.
• Multiplication of two numbers is equivalent to adding the corresponding exponents. Given and . Define. We know that the integer k can be expressed as the product of powers of primes: . It follows that for all .
• Example:

• Any integer of the form pn can be divided only by an integer that is of a lesser or equal power of the same prime number pj with j
n. Thus, we can say the following:
• Given and . If a|b then for all p.

Fermat’s Theorem

• Fermat’s theorem states the following:
• If p is prime and a is a positive integer not divisible by p, then:
• If p is prime and a is a positive integer, then: .
• Euler’s Totient Function:
• Euler’s totient function written as , defined as the number of positive integers less than n and relatively prime to n. By convention, .
• It should be clear that for a prime number p, .
• Now suppose that we have two prime numbers p and q, with . Then we can show that for .
• .
• Euler’s Theorem:
• Euler’s theorem states that for every a and n that are relatively prime:

Discrete Logarithms

• Discrete logarithms are fundamental to a number of public-key algorithms, including Diffie-Hellman key exchange and the digital signature algorithm (DSA).
• More generally, we can say that the highest possible exponent to which a number can belong (mod n) is (n). If a number is of this order, it is referred to as a primitive root of n. The importance of this notion is that if a is a primitive root of n, then its powers are distinct (mod n) and are all relatively prime to n. In particular, for a prime number p, if a is a primitive root of p, then .
• for any integer b and a primitive root a of prime number p, we can find a unique exponent i such that

1

• This exponent i is referred to as the discrete logarithm of the number b for the base a (mod p). We denote this value as dloga.p(b).
• Properties of Discrete Logarithms:
• dloga.p(1) = 0 -> a0mod n = 1
• dloga.p(a) = 1 -> a1 mod n = a
• dloga.p(XY) = dloga.p(X) + dloga.p(Y)
• dloga.p(XY) = Y dloga.p(X).

## 5 thoughts on “Slight Introduction to Number Theory”

1. […] This post was mentioned on Twitter by Abdelrahman Al-Ogail. Abdelrahman Al-Ogail said: has a new blog post "Slight Introduction to Number Theory" http://lnkd.in/PkRPZP […]

2. sherifshenko says:

nice Abdelrahman…Go on 🙂