Diophantine Equations: Theorem

Loading...

Del curso dictado por University of California San Diego

Number Theory and Cryptography

144 calificaciones

University of California San Diego

Number Theory and Cryptography

144 calificaciones

Curso 4 de 5 en SpecializationIntroduction to Discrete Mathematics for Computer Science

We all learn numbers from the childhood. Some of us like to count, others hate it, but any person uses numbers everyday to buy things, pay for services, estimated time and necessary resources. People have been wondering about numbers’ properties for thousands of years. And for thousands of years it was more or less just a game that was only interesting for pure mathematicians. Famous 20th century mathematician G.H. Hardy once said “The Theory of Numbers has always been regarded as one of the most obviously useless branches of Pure Mathematics”. Just 30 years after his death, an algorithm for encryption of secret messages was developed using achievements of number theory. It was called RSA after the names of its authors, and its implementation is probably the most frequently used computer program in the word nowadays. Without it, nobody would be able to make secure payments over the internet, or even log in securely to e-mail and other personal services. In this short course, we will make the whole journey from the foundation to RSA in 4 weeks. By the end, you will be able to apply the basics of the number theory to encrypt and decrypt messages, and to break the code if one applies RSA carelessly. You will even pass a cryptographic quest! As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

De la lección

Euclid's Algorithm

This week we'll study Euclid's algorithm and its applications. This fundamental algorithm is the main stepping-stone for understanding much of modern cryptography! Not only does this algorithm find the greatest common divisor of two numbers (which is an incredibly important problem by itself), but its extended version also gives an efficient way to solve Diophantine equations and compute modular inverses.

Least Common Multiple8:16

Diophantine Equations: Examples5:20

Diophantine Equations: Theorem15:38

Modular Division12:12

Conoce a los instructores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

In this video, we're going to show how to solve Diophantine equations

using the Euclid's algorithm for computing the greatest common divisor.

The essence of our approach is the following theorem.

Given three integers, a, b and c, where not both of a and b are equal to zero.

Consider the following Diophantine equation, ax + by = c.

The theorem states that this equation has a solution if and

only if the greatest common divisor of a and b divides c.

Okay, so this is the necessary and sufficient condition for

this Diophantine equations to have integer solutions.

Okay, let's prove it.

So denote by d is the greatest common divisor of a and the b, and

assume that our equation has an integer solution.

So since d divides a and b and

it is actually the greatest common divisor of a and b,

we can represent a as dp and b as dq where p and q are integers.

Then, continue on to the solution xy where c = ax + by and

this is equal to d(px + qy) just because a = dp and b=dq.

So as we see d indeed divides c in this case, okay?

Now let's prove the remaining part, assume now that d divides c,

so our goal is to show that then our Diophantine equation has the solution.

So, since d is a greatest common divisor of a and b,

it can be represented using Euclid's,

extended Euclid's algorithm, as ax plus by, okay?

Then we know that c, I'm sorry, let's represent it as axy plus by bar,

okay, so x bar and y bar is the certificate in the sense of

the fact that d is the greatest common divisor of a and b.

Now we use the fact that c is divisible by d.

Let's represent that c as td and let's consider the following x and y.

X = t times x bar, and y = t times y bar.

So what we're going to show is that these particular x and

y is a solution to our Diophantine equation.

So indeed, ax + by = t times

ax bar + by bar, okay?

But this is equal to just t times d, which is equal to c, okay?

So in this case, indeed, xy is a solution.

So once again, we've just stated and proved, actually, that the necessary and

sufficient condition for Diophantinequation to have a solution.

And in this case, what is needed is that d divides d is the greatest

common divisor of a and b divides C.

Okay, so let's give an example.

Consider the following Diophantine equation 10 times x plus

6 times y is equal to 14, okay?

So extended, the extended Euclid's algorithm used as

the following representation for the greatest common divisor of 10 and 6.

So 2 is equal to 10 times minus 1 plus 6 times 2, right,

so [INAUDIBLE] to just multiply this equation by 7.

So 2 multiplied by 7 is equal to 14 and

we can also multiply it by 7 on the right-hand side.

This gives us 10 times minus 1 times 7 plus 6 times 2 times 7.

So in a sense, what we have here, this is our x and this is our y, right?

So if x is equal to minus 7, in this case, y is equal to 14, okay?

So this gives us one solution, okay?

Now let's consider another example, in this case,

391x + 299y is equal to minus 69, okay?

So once again, in this case,

the greater common divisor of these two coefficients is equal to 23.

And using the extended Euclid's algorithm,

we can represent it as the linear combination of these two numbers.

So the efficient of this linear combination is minus 3 and 4.

Now we can multiply this equation with minus 3.

So we can multiply 23 with minus 3.

This gives us minus 69, exactly what is needed.

On the right-hand side, we will have what was in the previous line times minus 3,

and again, what was in the previous line times minus 3.

So in this case, this is our x, this is our y.

So x = 9, y = minus 12, okay.

So this is one particular solution, but

it turns out in this case there is also another solution.

X is equal to minus 4 and y is equal to 5.

Again, it is very natural to ask at this point how to find all possible

solutions to Diophantine equation in case there is at least one solution of course.

So we're going to develop this method soon, but before doing this,

let's prove the following auxiliary lemma which is also called Euclid's Lemma.

So if n divides a times b and also the greatest common divisor of a and

n is equal to 1, then n necessarily divides b.

Okay, so this is proved as follows.

Since a and n, their greatest common divisor is equal to 1,

let's represent 1 as a linear combination of a and n.

Assume that ax and y are the coefficients of its linear combinations.

So we know that there are such integers x and y, such as ax plus ny is equal to 1.

And this x and y family can be actually easily found by Euclid's algorithm, okay?

So let's multiply this equation by b, what we get is axb plus nyb is equal to b.

Okay, now we know that ab is divisible by n,

which means that ab can be represented as km.

Now let's use the previous equation.

So b = axb + nyb, but now we know that

axb = n xk, right, just because ab is equal to km.

So what we see is that n is equal to m times xk plus yb,

so indeed n divides b, right, which proves the lemma.

Now let's go back to the question of how to find

all solutions of a particular Diophantine equation.

So I assume that we have two integers a and

b, such that the greatest common divisor is equal to d.

Let's also represent a as dp and b as dq, and

it seems that x0, y0 is a solution of a Diophantine

equation ax plus by is equal to c.

So it is a solution meaning that ax0 plus by0 is equal to c.

So this is just a true fact.

Then the theorem states that any other solution

to this particular Diophantine equation has the following form.

So x in this solution is equal to x0 plus dq,

where y is equal to y0 minus tp where t is any integer.

So once again, what we state here is there actually two statements here.

First of all is for any t by considering x0 plus tq and

y0 minus tp we get a solution.

And the second statement is that any other solution has the following form, okay?

Let's prove both these statements.

So first of all, the first one.

In this case, let me recall that we have a = dp, b = dq,

and we also know that x0, y0 is a solution, okay.

Then consider any other solution, any other two points x and

y defined by x0 plus tq and y0 minus tp.

So this is our nuclear xy, xy.

Okay, let's consider what happens if we compute a times this x plus b

times this y.

This will be equal to xa times x0,

it is this term, plus by0, which is this term,

plus t times aq, which is this term,

multiplied by a- t x bp, okay?

So this leaves us t times aq minus dp, okay, so just by the fact that x0 and

y0 is equal to c, we can replace this term by c.

On the other hand, we know that aq = bp, okay.

This is just because a = dp and b = dq.

Okay, so this is just equal to zero.

Okay, so this just cancels.

So this shows that any x and y of this form is a solution, okay?

So what remains to be shown is that any other solution has the following form.

So for this, let's just show that any to any two solutions

are actually different by, they differ as follows.

So to get one solution from another one, we need to add dq to x and

subtract dp from y.

So for this, consider such two solutions x1, y1 and x2, y2.

So we know that ax1 plus bx, by1, I'm sorry,

is equal to c, and the same holds for x2, y2.

So this means that we can subtract one form another.

So listen from the other ones.

So this will leave us the following equation.

A times x1 minus x2 plus b times y1 minus y2 = 0.

Okay, so this our equation.

Okay, so in this case, let's divide this equation by d.

What we will get is the following.

So a divided by d is equal to p, b divided by d is equal to q.

So this is our new equation, okay?

Now, what we know is that the greatest common divisor of p and

q is equal to 1, okay?

This allows us to conclude, since this is divisible by q and

this is divisible by q, we know that this is divisible by q.

On the other hand, p and q is the greatest common divisor of p and q = 1,

which means that x1 minus x2 by Euclid's lemma should be divisible by q, right?

So we can represent x1 minus x2 by tq.

This already shows us the two x's are different by a multiple of q, right?

This is actually x1 minus x2 = tq.

And in this case, if we plug this tq into this equation, this will give us

the difference of y1 minus y2 = tp.

So exactly what we needed to prove.

So this concludes the proof of this lemma as it allows us to express all

solutions to the Diophantine equations over some initial single solution, okay.

Let's finally show an example of applying this lemma.

So once again in this case, we have three pesos times nine

equals three bills of three pesos, so

this is 27 plus five is equal to, I'm

sorry it should be minus five is equal to 22.

Okay, it should be plus five times minus one.

Okay so in this case, we are solving the following

Diophantine equation, 3x + 5y = 22.

And we know that there is a single solution,

at least one solution to this problem, expressed as follows.

x0 = 9, y0 = minus 1, okay?

Let me also recall that in this particular case, a is equal to three, b is

equal to five and their greatest common divisor denoted by d is equal to one.

So in this case, the numbers p and q are also equal to three and five.

So b is just equal to a,

q is equal to p just because the greatest common divider is equal to one.

So that our theorem states that any other solution is expressed through

our initial solution, which is as follows: 9 minus 1 as follows.

It is 9 plus 5t, this is x and

y is minus 1 minus 3t, okay.

So this gives us the whole range of solutions.

So for any integer t, this gives us a new solution, okay.

Assume at the same time recal that in our case we would like x and

y, we would like x to be non-negative and y to be non-positive actually, right?

So in this case, this translates to the following set of inequalities.

So we would like 10 plus 5t to be at least 0 and

we would like minus 1 minus 3t to be at most 0, okay?

So just by solving this through simple inequalities, we get,

the t should be at least minus 3, okay?

And since t must be an integer, it just means the t should be non-negative.

So what we get in the end is that any solution x = 9 plus 5t and

y = minus 1 minus 3t g gives us a valid

solution to our Diophantine equation.

For example, by taking t = 10,

you get a solution x = 59 and y = minus 31.

Which means that if you give 59 three peso bills to the cashier and

the cashier returns to you 31 five peso bills and

one apple, this will be a fair trade.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play