Diophantine Equations: Examples

Loading...

Do curso por University of California San Diego

Number Theory and Cryptography

67 classificações

University of California San Diego

Number Theory and Cryptography

67 classificações

Curso 4 de 5 em Specialization Introduction 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.

Na lição

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

Conheça os instrutores

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

Our second example, our second application of the Euclid's

algorithm is solving Diophantine equations.

These are polynomial equations in integer variables,

named after the ancient Greek mathematician, Diophantus.

Okay, so to introduce these equations, imagine the following situation.

Imagine that you are at Cuba and you would like to purchase an apple.

The price of an apple is 22 pesos.

So the problem is that you only have 3-peso bills.

And the cashier, in turn, only has 5-peso bills.

So what you would like to do is to give the cashier some number of 3-peso bills.

And in return you would like the cashier to give you 5-peso

bills plus an apple whose price is 22 pesos.

So in a sense what you would like to do is to solve

the following Diophantine equation.

3x = 22 + 5y, where x is the number of bills

that you're going to give to the cashier.

And y is the number of 5-peso bills that the cashier is going to give you.

So in particular, for this equation,

there is a solution where x is equal to 9 and y is equal to 1.

So let's check that indeed it holds.

So this is 3 times 9, so this is 27.

This is 5 times 1, this is just 5.

And the price of the apple is 22, so indeed 27 = 5 + 22, right?

And it turns out that there is another solution.

So for example, you can use x = 14 and y = 4.

Let's check, once again, on the left-hand side we have 42,

right here we have 5 times 4 which is 20 plus the price of an apple which is 22.

So again, this is a solution.

So now imagine a different story.

So you have a receipt with two blots on it.

So what you can see from this receipt is that this is for some number of lamps.

The price of each lamp is $49.36 cents, I'm sorry.

What you also see is that the total price is some number ending with 7.29 and

you would like to recover all the missing information.

So the point is that in this case, again,

you are going to solve some Diophantine equation.

Let's try to come up with this equation.

So first of all, you know that there is some number of lamps denoted by x.

You know that the price of each lamp is 4,936 cents.

Okay, then let's denote by y, the number which is missing here.

So just by looking at this,

in this part of the receipt you conclude that y consists of three digits.

So y is some integer from 100 to 999.

So y is at least 100, and y is smaller than 1,000.

And you know that, in this case, the total,

in cents, is represented as follows.

It is 1,000 times y + 728.

So what you are going to solve in this case is the following

Diophantine equation.

So 4,936x = 100y + 728 where, again, x and

y are integers and we also have an additional

restriction that y has to be the small digit.

And it turns out that, in this case, the solution for

this problem, for this equation can be uniquely recovered.

So you can easily recover all the missing information here,

which gives you the following solution.

Now let's continue two more examples.

So for example, consider the following Diophantine

equation, 187x + 55y = 121.

So one solution, in this case, is given by x equal to 3 and y equal to minus 8.

So you can easily check that it is indeed a solution.

It turns out, again,

that there is another solution where x is equal to minus 2 and y is equal to 9.

In fact, there are infinitely many solutions for

this particular Diophantine equation.

Now let's consider one more Diophantine equation,

namely 187x + 55y = 45.

It turns out that for this particular equation, there are no solutions at all.

And then at this point, it is very natural to ask, why is that?

So when a Diophantine equation has a solution.

And this is exactly the subject of our next video.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play