Application of the Euclidean Algorithm

From Math Images

Jump to: navigation, search
Image:inprogress.png
Euclidean Rhythms
This image shows a pattern of music rhythms generated by Euclidean algorithm. To find out the process of generating music rhythms or how it sounds like, go to section Euclidean Rhythms.

Contents

Basic Description

For more information about Euclidean algorithm, please click Euclidean Algorithm.

A More Mathematical Explanation

Note: understanding of this explanation requires: *Number Theory, Algebra

What can I do with Euclidean algorithm? Euclidean Algorithm is very important and fundamental in alge [...]

What can I do with Euclidean algorithm? Euclidean Algorithm is very important and fundamental in algebra, in other number systems, classical mathematical problems, other applied algorithms, computer science and music.

Mathematical Application

Reducing Fractions

If we know the gcd(greatest common divisor) of the numerator and denominator, we can know if they are prime to each other or not and use the gcd to reduce fractions:

By Euclidean algorithm, we know that gcd(168, 64) = 8 as we discussed in Euclidean Algorithm.

\frac{64}{168} = \frac{8\times8}{21\times8} = \frac{8}{21}
\frac{28}{63} = \frac{4\times7}{9\times7} = \frac{4}{9}

Adding and Comparing Fractions

Simplify \frac{7}{64} + \frac{5}{168}.

You can actually use any common denominator and then add the two equations to simplify it, but using the smallest common denominator is the easiest way. To find the smallest common denominator, we need to find the least common multiple(lcm) of the two denominators, which is the product of a and b divided by gcd(a, b) :  lcm(a, b) = \frac{ab}{gcd(a, b)}

Solution:
By Euclidean algorithm, we know that gcd(168, 64) = 8.
So  lcm(64, 168) = \frac{64 \times 168}{8} = 1344 \quad \quad \quad \quad \frac{7}{64}+ \frac{5}{168} = \frac{7\times21}{64\times21} + \frac{5\times 8}{168\times8} = \frac{147 + 40}{1344} = \frac{187}{1344}

In this way, you don't need to reduce the fraction anymore because the denominator is the least common multiple of 64 and 168.

Given two fractions (\frac{5}{64}, \frac{7}{168} for instance) lcm(a, b) also helps us determine which fraction is larger:

\frac{5}{64} = \frac{105}{1344} > \frac{56}{1344} = \frac{7}{168}


Continued Fractions

How to change a fraction into a continued fraction? Well, we need the help of Euclidean algorithm.

Let a = b q_0 + r_0 with  0 \leqslant r_0 < b , then \frac{a}{b} = q_0 + \frac{r_0}{b} .

By analog:

\frac{a}{b} = q_0 + \frac{r_0}{b}
\frac{b}{r_0} = q_1 + \frac{r_1}{r_0}
\frac{r_0}{r_1} = q_2 + \frac{r_2}{r_1}

... ...

\frac{r_{n-3}}{r_{n-2}} = q_{n-1} + \frac{r_{n-1}}{r_{n-2}}
\frac{r_{n-2}}{r_{n-1}} = q_n

Do they look familiar to you? Don't they share similarities with division equations from Euclidean algorithm? Indeed, Euclidean algorithm is closely related to continued fractions.

As you've probably noticed, the second term on the right-hand side is the inverse of the left-hand side of the next equation, except in the last equation r_{n-1} divides  r_{n-2} . In that case, we can combine those equations together. Start with the first two equations:

\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{r_1}{r_0}}

Next, move on with the third equation. Substitute \frac{r_1}{r_0} with the inverse of the third equation:

\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{r_2}{r_1}} }

Every time, the fraction \frac{r_k}{r_{k-1}} could be replaced by the inverse of the next equation. Keep this process till we hit the last equation and we will eventually get a continued fraction:

\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{1}{q_3 + \cfrac{1}{\ddots + \cfrac{1}{q_n}}}}}

Example:

Rewrite the fraction \frac{168}{64} as continued fractions.

Apply Euclidean algorithm:

168 = 2 \times 64 + 40
64 = 1 \times 40 + 24
40 = 1 \times 24 + 16
24 = 1 \times 16 + 8
16 = 2 \times  8 + 0

Therefore we could rewrite the fraction above as:

\frac{168}{64} = 2 + \cfrac{1}{1+\cfrac{1}{1 + \cfrac{1}{1+ \cfrac{1}{2} } } }


Linear Diophantine Equations

Suppose a, b and c are integers, linear Diophantine equations take the form ax + by = c and only have integer solutions. The equations honor the Greek mathematician Diophantus around the 3rd century A.D., who was interested in finding integer solutions to various equations in his whole life. See the figure below.

An example of linear Diophantine equation.
An example of linear Diophantine equation.

Theorem:

The linear Diophantine equation ax + by = c has a solution if and only if gcd(a, b) divides c.

Proof:

Because gcd(a, b) divides a and b, gcd(a, b) divides ax + by for any integer x and y. Thus, assume gcd(a, b) = am + bn, where m and n are both integers, and gcd(a, b) also divides c because c = ax + by.

Therefore, c = c' gcd(a, b) = c'(am + bn) = (c'm)a + (c'n)b.

Therefore, x = c'm, y = c'n are the two coefficients we want.

We could solve for the coefficients in this way by using extended Euclidean algorithm (see the section we talked about before extended Euclidean algorithm ). If c is not the gcd nor is it a multiple of the gcd, then this equation has no solution. So Diophantine equations either have infinite solutions or no solution.

Example:

Now let's find out how to solve a linear Diophantine equation with extended Euclidean algorithm.

348x + 126y = 6

First, find out if it has a solution or not. Start by going through the steps of the Euclidean algorithm to show that gcd(348, 126) = 6:

Eq. 1        348 = 2 \times 126 + 96
Eq. 2        126 = 1 \times 96 + 30
Eq. 3        96 = 3 \times 30 + 6
Eq. 4        30 = 6 \times 5

Indeed, 6 is the gcd of 348 and 126. The equation has solutions.

Then solve for integers x and y.

According to Eq. 3,  6 = 96 - 3 \times 30 .

According to Eq. 2,  30 = 126 - 1 \times 96 . Substitute it into the previous equation above, and we get

 6 = 96 - 3 \times (126 - 1\times 96)
 6 = -3 \times 126 + 4 \times 96

According to Eq. 1,  96 = 348 - 2 \times 126 . Substitute it into the previous equation above, and we get

 6 = -3 \times 126 + 4 \times ( 348 - 2\times 126)
\therefore 6 = 4\times 348 - 11\times 126

Therefore, x = 4 and y = -11.

Summary: In order to get the values of x and y, we need to keep trying to express gcd(348, 126) as an integer linear combination of 348 and 126 using equations from Euclidean algorithm step by step.


Chinese Remainder Theorem

There are certain things whose number is unknown. Repeatedly divided by 3, the remainder is 2; by 5 the remainder is 3; and by 7 the remainder is 2. What will be the number?

A problem like this is called Chinese remainder problem, another classical application of Euclidean algorithm. It is posed by a Chinese mathematician, Sun Tsu, in 4th century A.D.

More mathematically, we could rewrite the Chinese remainder theorem in the following way.

Theorem:

x \equiv a_1 \pmod{m_1}
x \equiv a_2 \pmod{m_2}
x \equiv a_3 \pmod{m_3}

... ...

x \equiv a_n \pmod{m_n}

where m_1, m_2, m_3, ... , m_n are relatively prime to each other or (m_i, m_j) = 1 for i \ne j . Then this system of congruences has a unique solution  mod~m_1m_2m_3...m_n.

Notation:

1. Before we prove this theorem, we need to know the modular arithmetic:

  • Modular arithmetic is an abstraction of a method of counting. For example, if I tell you today is Thursday, you know that it will be Wednesday in 20 days. Because 20 = 7 \times 2 + 6 , you just need to count 6 days beginning from Friday. Mathematically, we denote: a~mod~b = r, when a = qb + r, where q is the quotient and r is the remainder upon dividing integers a by b. Hence, 9~ mod~7   = 2, ~ ( 9 = 7 \times 1 + 2 ); 57~ mod~ 8  = 1, ~( 57 = 8 \times 7 + 1 ).
  • In general, if a and b are both integers and n is a positive integer, then a~ mod ~n = b~ mod~ n if and only if n divides a - b. Usually, we denote it as a \equiv b \pmod{n}. So x \equiv a_n \pmod{m_n} means m_n divides x and a_n or  x and a_n have the same remainder if divided by m_n.
  • The operation of modular arithmetic is, as what you probably expect, the same as regular operations: addition, subtraction, multiplication, and division. For example: if  x \equiv 1 \pmod{n} and  y \equiv 2x, then  y \equiv 2x \equiv 2 \cdot 1 \pmod{n} \equiv 2 \pmod{n}. Most of the time, we omit \pmod{n} if it is the same one in a continued equaity and just keep one at the end of this equality. So we could rewrite y as  y \equiv 2x \equiv 2 \cdot 1 \equiv 2 \pmod{n} .

2. Let l_k represents the product of all m's m_1m_2m_3\cdots m_n EXCEPT m_k, where k is any integer that is not greater than n. For example, l_3 = m_1m_2m_4m_5m_6m_7m_8.

Proof:

l_k = m_1m_2 \cdots m_{k-1}m_{k+1} \cdots m_n. Thus, l_k is prime to m_k, (l_k, m_k) = 1. By extended Euclidean algorithm , there exist integers s_k and t_k, such that  s_kl_k + t_km_k = 1. In terms of congruence, s_kl_k \equiv 1 \pmod{m_k}. We assume

Eq. 5        x \equiv a_1l_1s_1 + a_2l_2s_2 + \cdots + a_nl_ns_n

and we are going to prove that it is correct.

Now mod ~ m_k all the terms in Eq. 5, meaning that we divide the terms with m_k and obtaining the remainder. We only get a_kl_ks_k becausem_k could divide other terms, which eventually turn to 0, but not the k-th term ( the k-th term doesn't have m_k, so it is not a multiple of m_k). Therefore according to the operation of modular arithmetic:

Eq. 6        x \equiv a_kl_ks_k \pmod{m_k}

Because s_kl_k \equiv 1 \pmod{m_k}

 x \equiv a_k \cdot 1 \equiv a_k \pmod{m_k}.

Because k is no greater than n, Eq. 6 matches with the last equation from the description of the theorem x \equiv a_n \pmod{m_n}. This shows that x is, indeed, a solution to the system of congruence and we even have a formula for x, which is  :

Eq. 5        x \equiv a_1l_1s_1 + a_2l_2s_2 + \cdots + a_nl_ns_n.

Then we need to prove that it is the only solution to the congruence. Suppose there is another solution y.

y \equiv a_1 \pmod{m_1}
y \equiv a_2 \pmod{m_2}
y \equiv a_3 \pmod{m_3}

... ...

y \equiv a_n \pmod{m_n}

Compared with x, we will find that x \equiv a_k \equiv y \pmod{m_k}. Thus,  x- y \equiv 0 \pmod{m_k}.

Then m_k divides (x-y), or (x-y) is a multiple of all the m's.

Thus, the least common multiple(lcm) of m's divides (x-y), denoted as \left [m_1m_2m_3\cdots m_n \right ]\mid (x-y).

Because the m's are relatively prime, the least common multiples of all m's are actually the product of all m's, so we get \left [m_1m_2m_3\cdots m_n \right ] = m_1m_2m_3 \cdots m_n .

Hence, m_1m_2m_3 \cdots m_n \mid (x-y) or x \equiv y \pmod{m_1m_2m_3\cdots m_n} .

Here, we know that x and y are the same solution. Therefore, there is one unique solution to the congruence: mod ~ m_1m_2m_3\cdots m_n.

Example:

Go back to the original Chinese Remainder problem. Solve

x \equiv 2 \pmod{3}
x \equiv 3 \pmod{5}
x \equiv 2 \pmod{7} .

___________________________________________________________

The famous Chinese remainder problem: There are certain things whose number is unknown. Repeatedly divided by 3, the remainder is 2; by 5 the remainder is 3; and by 7 the remainder is 2. What will be the number? This figure shows that 23 is one possible answer.
The famous Chinese remainder problem: There are certain things whose number is unknown. Repeatedly divided by 3, the remainder is 2; by 5 the remainder is 3; and by 7 the remainder is 2. What will be the number? This figure shows that 23 is one possible answer.

Since 3, 5 and 7 are pairwise relatively prime, there is only one solution mod~3\times5\times7, which is mod~105.

As we did in the proof, we need to construct the formula for x:x \equiv a_1l_1s_1 + a_2l_2s_2  + a_3l_3s_3.

We know a_1 = 2, a_2 = 3 and  a_3 = 2, so let's find l_k and  s_k.

l_1 = m_2 \times m_3 = 5 \times 7 = 35.
l_2 = m_1 \times m_3 = 3 \times 7 = 21.
l_3 = m_1 \times m_2 = 3 \times 5= 15..

Because  l_1s_1 \equiv 1\pmod{m_1}

Therefore 35 s_1 \equiv 1\pmod{3}

To fin the value of integer s_1, try each integer starting with 1 until we get the remainder 1 when we divide (35 s_1) by 3.

We find that \quad s_1 = 2.

Similarly, 21 \times 1 \equiv 1 \pmod{5}, 15 \times 1 \equiv 1 \pmod{7} . We find that  s_2 = 1, s_3 =1 . Thus,

 x \equiv a_1l_1s_1 + a_2l_2s_2  + a_3l_3s_3
x \equiv 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 \equiv 233

 233 = 105 \times 2 + 23, therefore 233 \equiv 23 \pmod{105}  .

 233 = 105 \times 1 + 128, therefore 233 \equiv 128 \pmod{105} .

Therefore, the number is 23 or 128. See the right figure to check the smaller number 23.


Gaussian Integers

Gaussian integers are complex numbers a + bi, where a and b are real integers and i is the imaginary integer. The formal set of Gaussian integers is

Z[i] = \left\{ a + bi \mid a, b \in Z \right\}.

Gaussian integers satisfy the analog of Fundamental Theorem of Arithmetic by applying the analog of the Euclidean algorithm. In other words, a Gaussian integer has a unique factorization with certain prime factors multiplied together just as a natural integer does.

To prove that natural integers satisfy the fundamental theorem of arithmetic, we use Euclidean algorithm to find the gcd and list all the prime factors. We use the same method to show unique factorization of Gaussian integers. Please note, Euclidean algorithm is not the only effective way to prove this property, but it is the most convenient method.

First, denote \alpha, \beta as two Gaussian integers just as we denote a and b for two normal integers. Then, we start the process as we did for Euclidean algorithm: subtracting the smaller integer from the bigger one and obtaining a remainder that is strictly smaller than its predecessor from each step until it is 0. The general equation is the same,

r_{n -2} = k_{n - 1}r_{n -1} + r_n
lattice points in the complex plane
lattice points in the complex plane

but the quotients and remainders are complex numbers, starting withr_{n - 2}= \alpha, r_{n - 1} = \beta . You can treat those complex numbers separately as two parts, the real part and imaginary part. Then, we round the real and imaginary parts to the nearest integers. For example: \alpha = 2 + 3i, \beta = 1 + i.

\frac{a}{b} = \frac{2 + 3i}{1+ i} = \frac{(2 + 3i)(1 - i)}{(1+ i)(1 - i)} = \frac{2 + 3i - 2i - 3i^2}{1 - i^2} = \frac{2 + i + 3}{1 + 1} = \frac{5 + i}{2} = \frac{5}{2} + \frac{1}{2} i .

By rounding \frac{5}{2} to 2 and \frac{1}{2} to 0, we know that the quotient of \frac{a}{b} is 2 + 0\times i = 2 + 0 = 2. Thus, the remainder is 2 + 3i - (1 + i)\times 2 = i. Repeat this step by applying Euclidean algorithm in this way and we will get the gcd(\alpha, \beta), which is the last nonzero remainder. Note that there is going to be four greatest common divisor of \alpha and \beta up to multiplication by +1, - 1, + i, - i.

For normal integers, it is easy to know which one is bigger. How do we compare Gaussian integers to see which one is bigger and which one is smaller when they are complex numbers? Graphically, we represent Gaussian integers with lattice points in the complex plane (a, b). We take the norm of every Gaussian integer  \left\vert Z \right\vert = \sqrt{a^2 + b^2}, converting complex numbers to normal integers. See the right figure. The norm of the remainder decreases after each step of the Euclidean algorithm, meaning that it is getting closer to the origin. Therefore, we compare the distance from the point to the origin to see which Gaussian integer is smaller.

We can solve other applications and problems of the Euclidean algorithm for Gaussian integers as well, not only for normal integers. Applications like Chinese remainder theorem and linear Diophantine equations we discussed just now also work for complex numbers.


Musical Application

Euclidean Rhythms

In addition to those applications of various mathematical problems and computer science, Euclidean algorithm could be used to generate a large number of traditional musical rhythms efficiently.

Generally, binary sequences are used to represent musical rhythms. Each bit is considered as one unit of time; a one bit “x” means an onset of a note whereas an unaccented note “.” means a silence. Given a certain amount of notes, we will get a pattern if we distribute the notes as evenly as possible in a certain period. For example: assume that the time interval is 12 and there are four notes to be played, then this is how we note them:

x . . x . . x . . x . .

This is a very basic pattern since it gives you one note in every three steps. What if the time interval could not be divided exactly? Let’s say we want to play 5 notes during the time interval 12 instead of 4. Since 12 - 5\times2 = 2. First, we are going to start with a sequence of putting the same notes together:

x x x x x . . . . . . .

Then place a period after each x, which leaves 2 periods at the end:

[x . ] [x . ] [x . ] [x . ] [x . ] . .

We now have five paired bits “x .” and a remainder of two single bits each. Next, put the remaining 2 periods after each “x .” sequence:

[x . . ] [x . . ] [x . ] [x . ] [x . ]

We now have two sequences of bits “x . .” and a remainder of three paired bits "x . " . Next, put the remaining 3 bits after each “x . .” sequence:

[x . . x . ] [x . . x . ] [x . ]

This gives us only one remainder of “x . “ with two sequences of bits “x . . x . ". Although we could continue the distribution by putting “x . ” in the middle of “x . . x . ” and “x . . x . ”, it doesn’t matter because the sequence is cyclic (according to Bjorklund’s stopping rule). Therefore, the final sequence of 5 notes in an interval of 12 is:

x . . x . x . . x . x .

Did you find Euclidean algorithm lying in this process? When applying the Euclidean algorithm, we basically try to subtract the smaller number from the greater one again and again. The remainder is subtracted from the smaller number each time, generating a new remainder smaller than the quotient. We stop until the new remainder is zero. Let's go back to the process of finding a certain pattern of musical rhythms we did just now. When we pair up the 5 x’s and 7 periods and leave the two periods alone, we are doing the same thing as subtracting 5 (smaller number) from 12 (bigger number) twice and obtaining a remainder 2. This process mentioned above is actually called Bjorklund’s algorithm named after its creator. Bjorklund’s algorithm has the same principle and structure as Euclidean algorithm, so we now usually call these rhythms Euclidean rhythms.

Try this pattern by knocking on the table and you will probably find that it is not so regular compared with patterns whose notes divide evenly into the interval. Combine several different patterns to find their own beauty of showing unique musical rhythms. Go to Wouter’s website to generate your own rhythms with a cool flash application or watch the video of some beautiful rhythms Wouter has made!



RSA Algorithm and Modular Multiplication Inverse

RSA algorithm is invented by and named after Ron Rivest, Adi Shamir and Leonard Adleman in 1977. It is a widely used public key algorithm for encryption and digital signatures. It gets its security from integer factorization.

RSA
RSA

Operation

RSA algorithm has three steps: key generation, encryption and decryption. See the right figure.

Key Generation

We need a public key and a private key to do RSA algorithm. A public key, used for encrypting messages, is known to everyone. A private key, used for decrypting messages, is only known to the consignee. Messages encrypted with the public key can only be decrypted using the private key. This key generation is performed a single time for each person with the public and private keys.

  1. Pick any two different prime integers: p, q.
  2. Get the modulus n: n = p \times q .
  3. According to Euler's totient function, we have \phi (n) = (p - 1) \times (q - 1) . It is because n, the product of p and q, is bigger than \phi(n) and it is prime to n because prime numbers, p and q, have no common positive factors with p - 1 and q - 1 other than 1.
  4. Take any integer e, such that gcd(\phi(n), e) = 1 where  1 < e < \phi(n), which means that e and \phi are relatively prime. Now e is the public key component. (n, e) is the public key, used for encryption.
  5. Let d = e^{-1} mod~\phi(n) . It is usually found by extended Euclidean algorithm, which we will talk about in the next section. Now d is the private key component; you cannot give it to the public. The private key is (n, d), used for decryption.

Imagine you have the public key and private key now. You only give the public key to your friend A and A wants to send a secret message to you. This is what A should do.

Encryption

  1. Turn the message into an integer m with 0 < m < n.
  2. Compute t, where t = m^e ~ (mod~n).
  3. t is the encrypted message A gives to you. If you want to know what A wants to tell you, use the private key (n, d) to decrypt the code.

Decryption

  1. Compute m, where  m = t^d ~ (mod~n).
  2. You are able to recover the original message m now. This is the RSA algorithm.

Too hard to understand? No worries! There is going to be an example later.

RSA and extended Euclidean algorithm

This will give you a better understanding of how important extended Euclidean algorithm means to RSA algorithm. Modular multiplicative inverse, used to get the value of the private key, is an essential step in RSA, and extended Euclidean algorithm helps us solve modular multiplicative inverse.

How should we get d using extended Euclidean algorithm?

d = e^{-1} mod~\phi(n)

Here, it is complicated to solve the inverse of e directly, so we apply modular multiplicative inverse. The modular multiplicative inverse of an integer a modulo m is an integer x such that a^{-1} \equiv x ~(mod~m). This is equivalent to a a^{-1} \equiv a x \equiv  1~(mod~m).

( Note that the sign \equiv means equivalent. When terms on both sides are modulo m, the sign \equiv has the same function as the equal sign =. To help you understand better about modular multiplicative inverse, we can rewrite those equations above, though mathematically inappropriate, as:
Because a^{-1} = x, a^{-1} a = 1, so  a x = 1. )

In this case, denote x as the remainder of e^{-1} modulo m, such that e^{-1} \equiv x~(mod~\phi(n) ) , so

d \equiv e^{-1} \equiv  x~mod~\phi(n) .

Now we just need to know x's value to get the value of d. According to modular multiplicative inverse, e^{-1} \equiv x~(mod~\phi(n) ) , hence

e e^{-1} \equiv ex \equiv 1~(mod~\phi(n)).

By the definition of congruence, it means that we divide ex with \phi(n) and get a remainder 1. This could be noted as

ex - \phi(n) y = 1 where x and y are integers.

Recall that e and \phi(n) are coprime integers, so gcd(e, \phi(n)) = 1. Therefore,

ex - \phi(n)y = gcd(e, \phi(n)).

Recall that our goal is to find the value of x. Does this equation look familiar to you? Yes, it is in the form of Bézout's identity. In section extended Euclidean algorithm, we know that extended Euclidean algorithm can solve for the two coefficients x, y of Bézout's identity:

ax + by = gcd(a, b) .

Solve ex + \phi(n) (- y) = gcd(e, \phi(n)) for x using extended Euclidean algorithm, and then we will know the value of d. Now we can tell that extended Euclidean algorithm is very important for RSA algorithm.

Security

RSA algorithm is pretty secure. If people want to attack RSA, they have to fix the problem of factoring large numbers and the RSA problem. We won't talk about these two problems in detail, but what is worth mentioning is that full decryption of the RSA ciphertext is infeasible because there hasn't been an efficient way of solving the two problems so far.




Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.

About the Creator of this Image

As he said in his webpage, Wouter Hisschemöller is interested in lots of different aspects of audio, music and (ActionScript) programming: Manipulating existing sounds (like samplers do), generating new sounds (like synthesizers), capturing and storing musical data (as used in composition, sequencers and MIDI) etc.



References

[1] Loy, Jim. Euclid's Algorithm. Retrieved from http://www.jimloy.com/number/euclids.htm.

[2] Artmann, Benno. (1999) ‘‘ Euclid-the creation of mathematics.’’ New York: Springer-Verlag.

[3] Weisstein, Eric W. Euclidean Algorithm. From MathWorld--A Wolfram Web Resource. Retrieved from http://mathworld.wolfram.com/EuclideanAlgorithm.html.

[4] Klappenecker, Andreas. Euclid's Algorithm. Retrieved from http://faculty.cs.tamu.edu/klappi/alg/euclid.pdf.

[5] Wikipedia (Linear Diophatine Equation). (n.d.). Linear Diophantine Equation. Retrieved from http://en.wikipedia.org/wiki/Linear_diophantine_equation.

[6] W. H. Freeman and Company. The Euclidean Algorithm and Linear Diophantine Equations. Retrieved from http://www.math.mtu.edu/mathlab/COURSES/holt/dnt/euclid.html.

[7] Gallian, Joseph A. (2010) Contemporary Abstract Algebra Seventh Edition. Belmont: Brooks/Cole, Cengage Learning.

[8] Bogomolny, Alexander. Chinese Remainder Theorem. Retrieved from http://www.cut-the-knot.org/blue/chinese.shtml.

[9] Ikenaga, Bruce. The Chinese Remainder Theorem. Retrieved from http://marauder.millersville.edu/~bikenaga/numbertheory/chinese-remainder/chinese-remainder.html.

[10] Wikipedia(Gaussian Integer). (n.d.). Gaussian Integer. Retrieved from http://en.wikipedia.org/wiki/Gaussian_integer.

[11] Toussaint, Godfried. The Euclidean Algorithm Generates Traditional Musical Rhythms. Retrieved from http://cgm.cs.mcgill.ca/~godfried/publications/banff.pdf.

[12] Hisschemöller, Wouter. Euclidean Rhythms. Retrieved from http://www.hisschemoller.com/2011/euclidean-rhythms/comment-page-1/#comment-4509.

[13] Voytko, Jake. Why Does RSA Work? Retrieved from http://www.jakevoytko.com/blog/2008/01/06/why-does-rsa-work/#totient.

[14] Wikipedia(RSA). (n. d.). RSA. Retrieved from http://en.wikipedia.org/wiki/RSA.

Future Directions for this Page

  1. Application about knot theory.
  2. Anything you think necessary for this page.



If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.






Personal tools