Discrete Mathematical Structures

1. [10 points] concrete calculations

(a) (4 points) Ex press the numbers 735 and 126 as products of primes . Compute GCD(735, 126)
and LCM (735, 126).

[Answer]


(b) (3 points) Which of the fol lowing equations are correct? Show work or a very brief explanation.
[Answer]

•

Expanding the definition of mod, for some q ∈Z:



We conclude -6 is equivalent to 6, (mod 12).

•

As before, for some q ∈Z:

17 = 10 + 3q
7 = 3q

Both 3 and 7 are prime numbers, thus one cannot be a multiple of the other . We
conclude the equivalence does not hold.

• 

Finally, for some q ∈Z:

17 = 9 + 4q
8 = 4q
q = 2. (2)

We conclude that 17 is equivalent to 9, (mod 12).

(c) (3 points) Use the Euclidean algorithm (lecture 8, p 229 in Rosen) to calculate GCD(1529, 14039).
Show your work.

[Answer]
For a common divisor d ∈Z between two integers a, b ∈ Z, we have that if a = bq + r,
for some r ∈Z, 0≤ r < b, then d also divides r. Furthermore, if d is the largest of
such divisors, we have that GCD(a, b) = GCD(b, r). We can iterate this idea, noting that
GCD(a, 0) = a:
 

GCD(1529, 14039) = GCD(139, 0) = 139.

2. [5 points] negating quantified statements
The definition of GCD can be made more precise as follows. Suppose that x and y are integers,
not both zero . Suppose that t is an integer. Thent is the GCD of x and y iff

(a) t is a common divisor of x and y (i.e. ), and
(b) if d is any common divisor of x and y, then d ≤t.

State precisely what it means for an integer t NOT to be the GCD of x and y. Phrase your
answer so that any negations are on individual predicates rather than on complex expressions .

[Answer]
This question asks for the INVERSE of the statement “t is the GCD of x and y iff (a) and (b)”.
Negating the first part we have:
“t is NOT the GCD of x and y”.
For the second part, the negation of (a) is:
“t is NOT a common divisor of x and y.”
For the statement in (b), it is helpful to clearly write it in terms of a universal quantifier:
“For all the common divisors d of x and y, d  ≤t.

Negating the previous statement:


Which we can translate to English into something like : “There is a common divisor of x
and y that is greater than t”. Negating the whole second part “(a) and (b)”, and using De
Morgan’s law yields “not (a) or not (b)”. Putting the previous steps together, we have:

t is not the GCD of x and y iff

(a) t is not a common divisor of x and y, or
(b) there is a common divisor of x and y that is greater than t.

3. [10 points] proof using the divides relation

Prove the following claim. Direct proof should work ok.

Claim 1. For any positive integers m and n, m and n both greater than 1, if n l m and a b
(mod m), then a b (mod n).

[Answer]
Since , we can write:
m = kn, for some k ∈Z.
Also, given the equivalence relation on a and b, we can write:
a = b + qm, for some q ∈Z.
Using m = kn in the previous equation yields :
a = b + kqn.
Given that kq∈Z, using the definition of (mod n) we have that:
.

4. [10 points] proof by contradiction

Consider the following claim:

Claim 2. For any integers a,b,and c, if a and b are multiples of 7 and c is not a multiple of 7,
then the equation ax + by = c has no solutions where x and y are both integers.

(a) State the negation of this claim.
[Answer] Let p be the statement “a and b are multiples of 7”, let q be the statement
“c is not a multiple of 7”, and let r be the statement “the equation ax + by = c has no
solutions where x and y are both integers”. We need to negate the statement :


Shuffling around this last statement (commutative law) for a better wording, in English
it reads:

“For any integers a, b, and c, the equation ax + by = c HAS solutions where x and y are
both integers, with a and b being multiples of 7, and c not being a multiple of 7”.

(b) Use proof by contradiction to show that the claim is true.

[Answer] For this second part, we need to prove that the statement we found in the first
part leads to a contradiction.
Given that a and b are multiples of 7, we can write them respectively as a = 7m, and
b = 7n, for some m, n∈Z. Therefore, we can rewrite the equation as:

ax + by = c
7mx + 7ny = c
7(mx + ny) = c.

We are as suming that m and n are integers , therefore mx + ny ∈Z. But this would
mean that c is a multiple of 7 too, which is a contradiction. Therefore our assumption
that m, n ∈Z is false, and this proves the original claim to be true.

5. [10 points] proof using floor

Recall that the floor of a real number x, i.e. , is defined to be the largest integer d such
that d ≤x.
Claim 3. For any real numbers x and y ,
(a) Explain briefly why it’s not true if you replace≥ with =.
[Answer] We can easily give a counterexample to . Consider x =

Which is a contradiction for addition of integers in the absence of other equivalence
relations.

(b) Prove that this claim is true.

[Answer] By the definition of , we know that for k ∈Z and x ∈R, k = iff
k ≤x < k + 1.
To prove the claim, first we need to prove an intermediate result:

For n ∈Z and x ∈R,.

Consider m = . We have:

m ≤x < m + 1

Adding n to the inequality:

m + n≤ x + n < m + n + 1.

This last inequality follows the form of the floor function for . Therefore we have
, which is the intermediate result we wanted to prove. Now
let us manipulate the left side of the original claim:


In this last step we just added and subtracted and , which does not modify the
equation. Now, using our intermediate result, given that are integers:

Note that , because . Similarly, we have that .
Therefore . Putting all this results together:

Which proves our original claim.

[Alternate Answer]
Of course, there are many (infintely?) different ways to prove this statement.
One alternative proof would be the following:
Since and y we can say
Now take the floor of both sides of this equation to get:
But since and are integers,
Thus,