Discrete Mathematics for Computer Scientists -- Assignment 5

Discrete Mathematics for Computer Scientists -- Assignment 5 - Arithmetic

DIT980, HT 2015

Fire | Forum | TimeEdit | Links | 2014

Assignment Week 5 - Arithmetic

Assignments

(1.) Consider the following two diophantine equations. For each one, explain whether or not it has a solution. If there are any solutions, give three different solutions.

(a) 17x + 22y = 6

(b) 22x - 55y = 13

(2.) Consider the following three congruences:

x ≡ 1 (mod 3)
x ≡ 2 (mod 5)
x ≡ 3 (mod 7)

(a) Find an integer x that satisfies all three congruences simultaneously. Use the Chinese Remainder Theorem, and explain how you reached your solution, step by step.

(b) What solutions are there such that 0 ≤ x ≤ 200?

(3.) Show that for all integer numbers x, it is never the case that x² ≡ 2 (mod 3).

Hint: Consider the remainder ("rest") when dividing x by 3.

Submission

Submission of this assignment should be done electronically through the Fire system.

The submission deadline is Wednesday, October 7, at 13:00. At this time, you should have submitted a serious attempt to solve the assignment. A serious attempt is either an answer you believe to be correct, or a partial answer plus a detailed explanation of what you have tried to come up with a full answer. An empty document is not a serious attempt.

After submitting, you have until October 19 (midnight) to submit a completely correct version.

You can submit your answers in any of the following formats:

A simple text file, ending in .txt. You can make text files in any text editor, and then upload it to the Fire system.
(When using a text file, you may sometimes need to "invent" notation. Please be clear about what your notation means. A list of suggested notation for text files is provided by us. You may also use Unicode.)
A picture you have made in a painting program, ending in .gif, .jpg, or .png. You can use for example MS Paint, or Google Docs to make a picture, and upload it to the Fire system.
A PDF-file, ending in .pdf. You can make PDF files by for example using OpenOffice, LibreOffice, Microsoft Word, or Google Docs, and choosing export as PDF. Then, upload the PDF-file to the Fire system.
A scanned in document, ending in .pdf or .jpg. You can write your answer on a piece of paper, and use a scanner to scan it in and convert to a PDF-file. Or you can use your mobile phone to take pictures of the papers, and upload these to the Fire system.

If you submit multiple files, please name and/or number them such that the order in which we should read them is obvious. You can also write a text file, and have it refer to pictures that you upload separately.