Description

CENG223
Discrete Computational Structures
Homework 3

Question 1
Use Fermat’s Little Theorem theorem the find (222 + 444 + 666 + 880 + 10110) mod 11 ≡ ?
Note: Fermat’s Little Theorem is provided in our book (Kenneth H. Rosen, Discrete Mathematics and Its Applications), and it is a prerequisite for this question. This means that your solution have to use Fermat’s Little Theorem.
Question 2
Find gcd(5n + 3,7n + 4) and while doing that, show the steps of Euclid’s algorithm clearly.
Question 3
Let x be a prime number,
If m2 = n2 + kx where m, n, and k are integer numbers.
Show that x|(m + n) or x|(m − n).
Question 4
Show that for all n such that n ≥ 1 the following is true:
(1)
Note: You have to use mathematical induction to prove that.
1
1 Regulations
1. You have to write your answers to the provided sections of the template answer file given. Other than that, you cannot change the provided template answer file. If a latex structure you want to use cannot be compiled with the included packages in the template file, that means you should not use it.
2. Do not write any other stuff, e.g. question definitions, to answers’ sections. Only write your answers. Otherwise, you will get 0 from that question.
3. Late Submission: Not allowed
5. Newsgroup: You must follow the odtuclass discussions (https://odtuclass.metu.edu.tr) for discussions and possible updates on a daily basis.
2 Submission
Submission will be done via odtuclass. Download the given template file, ”hw3.tex”, when you finish your exam upload the .tex file with the same name to odtuclass.
Note: You cannot submit any other files. Don’t forget to make sure your .tex file is successfully compiled in Inek machines using the command below.
$ pdflatex hw3.tex
2