# Introduction to Number Theory

## A simple intro to basic number theory concepts and their applications to the field of encryption.

This article is intended to show a simple introduction into number theory, and give readers some insight into the applications of number theory in encryption.

---------------------------------------Division---------------------------------------

The first piece of knowledge you need to make sense of this is division. Note that this is not just 10/2=5, this is a general definition of the concept which will be used later on in the article.

Definition:

a (such that a is not equal to 0) divides b if there exists k such that b = ak

This is denoted as: a|b (read as: a divides b)

Example:

- 3 | 7 false

- 3 | 12 true

Let a, b, c be integers. Then these are a few tautologies (something that is always true):

-If a|b and a|c , then a|(b + c)

-If a|b then a | bc

-If a|b and b|c then a|c

Ill prove the first tautology mathematically: a|b and a|c → a|(b + c)

- Assume a|b and a|c.

- b=ak1, c=ak2 where k1 and k2 are constants

- b+c=ak1 + ak2

- b+c=a(k1+k2)

- Since k1+k2 is an integer, by the definition of division a|b+c

---------------------------------------Modulus---------------------------------------

Definition:

a and b are integers, and m is a positive integer. a is congruent to b modulo m if m|(a-b).

-This is written as: a=b mod m

-a=b mod m if a%m=b%m where x%y is the remainder of x/y

Example:

-17%5=2, 12%5=2, therefore 17=12 mod 5

-3%10=7, 17%10=7, therefore -3 =17 mod 10

Here are a few tautologies (the first one being the most important in this case):

-a=b mod m if there exists k such that a=b+km. Note that this is equivalent to the definition shown above: m|(a-b)

-(a+b)mod m =((a mod m)+(b mod m)) mod m

-ac mod m=((a mod m)(b mod m)) mod m

-Let m be a positive integer. If a=b mod m and c=d mod m, then: a+c=b+d(mod m) and ac=bd(mod m)

Heres an example: Prove that if n is odd, then n^2=1 mod 8

There exists a k such that n=2k+1 (note that this is the definition of an odd number)

So, n^2=4k^2+4k+1

n^2-1=4k^2+4k

n^2-1=4k(k+1)

n^2=1 mod 8 is the same as 8|n2-1 which is the same as 8|4k(k+1)

4k(k+1)=8c reduces to k(k+1)=2c when you divide both sides by 4

Note that both k(k+1) and 2c are always even, and since k and c are just arbitrary constants, this is true.

Modulus is used in the definition for the Caesar Cipher:

E(x)=(x+k) mod 26 (note that the original Caesar Cipher used k=3)

Where E(x) is the encrypted text and x is the original text.

---------------------------------------Greatest Common Divisor---------------------------------------

The greatest common divisor of two integers a and b is the largest integer d such that d|a and d|b. This is denoted by gcd(a, b).

Two numbers are considered relatively prime if they dont have any common factors (besides 1).

Here is the link to the Euclidean algorithm for finding the gcd of two numbers: http://www.hellboundhackers.org/code/gcd-1218_python.html

This is written in python, but its a fairly simple algorithm that should be easy to convert into whatever language youre comfortable with.

---------------------------------------Multiplicative Inverse---------------------------------------

Given a=b mod m, there exists A such that aA=1 mod m

The inverse only exists if the gcd(a, m)=1

So, for example, 3A=1 mod 7

A must be equal to -2 since 3*(-2) is -6, and -6=1 mod 7 (since by definition, mod is a-b=mk, so -7=7k)

The inverse can be used in this type of situation: 3x=2 mod 5

To solve for x, you need to isolate it (i.e. get rid of the 3 in front)

The inverse of 3=2 mod 5 is 2, so multiply both sides by the inverse:

3xA=2A mod 5, so we get x=4 mod 5

If gcd(a, m) is not equal to one, you have to solve it differently. For example: 2x=2 mod 4

Break the problem down to the definition of modulus.

2x=2+4k Notice that everything is divisible by 2.

x=1+2k Now you can use the definition of modulus to change it back.

x=1 mod 2, therefore x=1 is a solution (note that there are many solutions)

-----------------------------------------------------------------------------------------------------

This can all be applied to when creating simple encryption algorithms and reversing them. For example, suppose that messages are encrypted using this formula: F(p)=(ap+b) mod 26 such that gcd(a, 26)=1 where p is the original data, a and b are integers, and F(p) is the encrypted data.

Heres how you can find the decryption algorithm:

First break the problem down using the definition of modulus: F(p)=26k+ap+b

Isolate p: F(p)-b+26k=ap

Convert it back to modulus form: ap=(F(p)-b) mod 26

Find the multiplicative inverse to solve for p: p=A(F(p)-b) mod 26

I hope you found this article to be interesting, and if so I can write another on this (or a similar) subject.

-Ynori7

---------------------------------------Division---------------------------------------

The first piece of knowledge you need to make sense of this is division. Note that this is not just 10/2=5, this is a general definition of the concept which will be used later on in the article.

Definition:

a (such that a is not equal to 0) divides b if there exists k such that b = ak

This is denoted as: a|b (read as: a divides b)

Example:

- 3 | 7 false

- 3 | 12 true

Let a, b, c be integers. Then these are a few tautologies (something that is always true):

-If a|b and a|c , then a|(b + c)

-If a|b then a | bc

-If a|b and b|c then a|c

Ill prove the first tautology mathematically: a|b and a|c → a|(b + c)

- Assume a|b and a|c.

- b=ak1, c=ak2 where k1 and k2 are constants

- b+c=ak1 + ak2

- b+c=a(k1+k2)

- Since k1+k2 is an integer, by the definition of division a|b+c

---------------------------------------Modulus---------------------------------------

Definition:

a and b are integers, and m is a positive integer. a is congruent to b modulo m if m|(a-b).

-This is written as: a=b mod m

-a=b mod m if a%m=b%m where x%y is the remainder of x/y

Example:

-17%5=2, 12%5=2, therefore 17=12 mod 5

-3%10=7, 17%10=7, therefore -3 =17 mod 10

Here are a few tautologies (the first one being the most important in this case):

-a=b mod m if there exists k such that a=b+km. Note that this is equivalent to the definition shown above: m|(a-b)

-(a+b)mod m =((a mod m)+(b mod m)) mod m

-ac mod m=((a mod m)(b mod m)) mod m

-Let m be a positive integer. If a=b mod m and c=d mod m, then: a+c=b+d(mod m) and ac=bd(mod m)

Heres an example: Prove that if n is odd, then n^2=1 mod 8

There exists a k such that n=2k+1 (note that this is the definition of an odd number)

So, n^2=4k^2+4k+1

n^2-1=4k^2+4k

n^2-1=4k(k+1)

n^2=1 mod 8 is the same as 8|n2-1 which is the same as 8|4k(k+1)

4k(k+1)=8c reduces to k(k+1)=2c when you divide both sides by 4

Note that both k(k+1) and 2c are always even, and since k and c are just arbitrary constants, this is true.

Modulus is used in the definition for the Caesar Cipher:

E(x)=(x+k) mod 26 (note that the original Caesar Cipher used k=3)

Where E(x) is the encrypted text and x is the original text.

---------------------------------------Greatest Common Divisor---------------------------------------

The greatest common divisor of two integers a and b is the largest integer d such that d|a and d|b. This is denoted by gcd(a, b).

Two numbers are considered relatively prime if they dont have any common factors (besides 1).

Here is the link to the Euclidean algorithm for finding the gcd of two numbers: http://www.hellboundhackers.org/code/gcd-1218_python.html

This is written in python, but its a fairly simple algorithm that should be easy to convert into whatever language youre comfortable with.

---------------------------------------Multiplicative Inverse---------------------------------------

Given a=b mod m, there exists A such that aA=1 mod m

The inverse only exists if the gcd(a, m)=1

So, for example, 3A=1 mod 7

A must be equal to -2 since 3*(-2) is -6, and -6=1 mod 7 (since by definition, mod is a-b=mk, so -7=7k)

The inverse can be used in this type of situation: 3x=2 mod 5

To solve for x, you need to isolate it (i.e. get rid of the 3 in front)

The inverse of 3=2 mod 5 is 2, so multiply both sides by the inverse:

3xA=2A mod 5, so we get x=4 mod 5

If gcd(a, m) is not equal to one, you have to solve it differently. For example: 2x=2 mod 4

Break the problem down to the definition of modulus.

2x=2+4k Notice that everything is divisible by 2.

x=1+2k Now you can use the definition of modulus to change it back.

x=1 mod 2, therefore x=1 is a solution (note that there are many solutions)

-----------------------------------------------------------------------------------------------------

This can all be applied to when creating simple encryption algorithms and reversing them. For example, suppose that messages are encrypted using this formula: F(p)=(ap+b) mod 26 such that gcd(a, 26)=1 where p is the original data, a and b are integers, and F(p) is the encrypted data.

Heres how you can find the decryption algorithm:

First break the problem down using the definition of modulus: F(p)=26k+ap+b

Isolate p: F(p)-b+26k=ap

Convert it back to modulus form: ap=(F(p)-b) mod 26

Find the multiplicative inverse to solve for p: p=A(F(p)-b) mod 26

I hope you found this article to be interesting, and if so I can write another on this (or a similar) subject.

-Ynori7

Comments

Zephyr_Pureon January 05 2009 - 01:22:20 Before the critics make it here, I'll go ahead and say that I was left wanting more at the end of this article. That could both be an indication of a very interesting article and an indication of an article that is a bit short. Number theory is a fascinating necessity when it comes to algorithmic comprehension, which can be applied to encryption, encoding, coding logic, and optimizing code. It's also enjoyable for closet mathematicians. Finally, this article is a prime example of how someone must think before they do... this applies to coding as well: Many people like to just jump into the code when, in fact, they should sit back and rationalize how the code will work first. So, though I felt like I hit an abrupt and unexpected halt at the end of the article, I quite enjoyed it. It was well-written and it gave information on a topic that gets very little attention here. Good job, man. |

yours31fon January 05 2009 - 01:32:12 Very nice. This makes a good start on coding and encrypting. Nice format and nice detail. I am with zephyr in wanting more, but all in all its is a good article. |

c4p_sl0ckon January 05 2009 - 10:54:32 Format and grammar was good. The content was interesting, and I agree with previous comments that there could have been a bit more. But I guess that leaves more for the next one. Keep it up. |

korgon January 10 2009 - 03:29:31 Nice article kept me interested like to see more. This is what we need on HBH. |

fallingmidgeton January 10 2009 - 07:45:29 I thought it was good. I understood some of it but after a while I get confused with just reading. Makes me want to get back into math again. Keep up the good work. |

Frost_Ton January 22 2009 - 03:00:32 I greatly enjoyed this. If I could guess I would assume you are taking/have taken a course in discrete mathematics? This article reminded me of mine thats for sure. I will agree with both Zephyr in that you should do a follow up/continuation of this article, and include more topics and content and with korg in that this is what we need here. Keep up the good work mate. |

Post Comment

**Sorry.**

You must have completed the challenge

**Basic 1**and have

**100 points**or more, to be able to post.