Math 1081 - Discrete Mathematics Assignment

Question 1

Prove that 𝒍𝒐𝒈𝟖𝟎 𝟓𝟎 is irrational

By assuming that 𝑙𝑜𝑔#$ 50 is rational and deriving a contradiction, we can prove that it is not
rational but irrational by showing that it cannot be expressed as a ratio of two integers.
%
Suppose 𝑙𝑜𝑔#$ 50 is rational, it can be written as a fraction &

𝑝
𝑙𝑜𝑔#$ 50 =
𝑞

in which p and q are integers, q ≠ 0

The above equation can now be written as:

Equations on both sides can be raised by the power of ‘q’:

80% = 50&

Using basic algebra and prime factorization, the above equation can be simplified as:

(2' × 5)% = (2 × 5( )&

2'% × 5% = 2& × 5(&

As the bases are same on both the sides of the equation, we can equate the exponents:

Equation with base 2:

4𝑝 = 𝑞

Equation with base 5:

𝑝 = 2𝑞

We substitute 𝑝 = 2𝑞 into 4𝑝 = 𝑞 to check if both the equations are true at the same time:

4(2𝑞) = 𝑞

8𝑞 = 𝑞
Since we already know that q = 0, we divide both sides by q:

8=1

Since this equation contradicts itself, our assumption of 𝑙𝑜𝑔#$ 50 being rational is incorrect,
Therefore, 𝒍𝒐𝒈𝟖𝟎 𝟓𝟎 is irrational.

Question 2

The relation /star is defined on the set ℤ by

𝒙 /star 𝒚 if and only if 𝒙𝒚 > 𝟎.

For each of the following questions, be sure to provide a proof supporting your answer.

a) Is /star reflexive?

A relation will be reflexive if for every integer 𝑥 ∈ ℤ, which is 𝑥 /𝑠𝑡𝑎𝑟 𝑥. We must have
𝑥 ( > 0.

Let us assume any integer 𝑥:

• If 𝑥 ≠ 0, then 𝑥 ( > 0, so 𝑥 /𝑠𝑡𝑎𝑟 𝑥 is true.

As there is at least one value for 𝒙 ∈ ℤ (𝒙 = 𝟎) For which 𝒙 /𝒔𝒕𝒂𝒓 𝒙 is not true, the
relation /𝒔𝒕𝒂𝒓 is not reflexive

b) Is /star symmetric?

A relation will be symmetric if for all 𝑥, 𝑦 ∈ ℤ, 𝑥 /𝑠𝑡𝑎𝑟 𝑦 ⟹ 𝑦 /𝑠𝑡𝑎𝑟 𝑥

This means that, 𝑥 /𝑠𝑡𝑎𝑟 𝑦 if and only if 𝑥𝑦 > 0. As multiplication is always commutative,
𝑥𝑦 = 𝑦𝑥. Therefore 𝑥𝑦 > 0 is also true.

Hence, if 𝒙 /𝒔𝒕𝒂𝒓 𝒚, then 𝒚 /𝒔𝒕𝒂𝒓 𝒙 and the relation /𝒔𝒕𝒂𝒓 is symmetric.

c) Is /star anti-symmetric?

A relation will be antisymmetric if for all 𝑥, 𝑦 ∈ ℤ,

(𝑥 /𝑠𝑡𝑎𝑟 𝑦 and 𝑦 /𝑠𝑡𝑎𝑟 𝑥) ⟹ 𝑥 ⟹ 𝑦.

We will test if this statement is aways true. Let us consider the integers 𝑥 = 2, 𝑦 = 4.
 • 𝑥𝑦 = 2 × 4 = 8 > 0, 𝑥 /𝑠𝑡𝑎𝑟 𝑦 is true.
• 𝑦𝑥 = 4 × 2 = 8 > 0, 𝑦 /𝑠𝑡𝑎𝑟 𝑥 is true.
• Both the above statements are true, however 𝑥 ≠ 𝑦.

Therefore, both 𝑥 /𝑠𝑡𝑎𝑟 𝑦 and 𝑦 /𝑠𝑡𝑎𝑟 𝑥 are true but 𝑥 ≠ 𝑦, which violates the condition for
anti-symmetry.

Hence, the relation /𝒔𝒕𝒂𝒓 is not anti-symmetric

d) Is /star transitive?

A relation /𝑠𝑡𝑎𝑟 will be transitive if for all 𝑥, 𝑦, 𝑧 ∈ ℤ, if 𝑥 /𝑠𝑡𝑎𝑟 𝑦 and 𝑦 /𝑠𝑡𝑎𝑟 𝑧, then
𝑥 /𝑠𝑡𝑎𝑟 𝑧.

Let us assume that 𝑥 /𝑠𝑡𝑎𝑟 𝑦 and 𝑦 /𝑠𝑡𝑎𝑟 𝑧:

𝑥𝑦 > 0 and 𝑦𝑧 > 0

We compare the signs of 𝑥, 𝑦, 𝑧:

• As 𝑥𝑦 > 0, both 𝑥 and 𝑦 will have the same sign (positive or negative) for 𝑥𝑦 to be
greater than 0
• As 𝑦𝑧 > 0, both will have the same sign as explained above

Therefore, in 𝑥𝑧, both will have the same sign. They can be either positive or negative but as
both are same sign, 𝑥𝑧 > 0, 𝑥 /𝑠𝑡𝑎𝑟 𝑧

This explanation and reasoning will be the same for all the combinations of 𝑥, 𝑦, 𝑧 ∈ ℤ in
which the conditions remain the same.

Therefore, the relation /𝒔𝒕𝒂𝒓 is transitive.

e) Is /star an equivalence relation, a partial order, both, or neither?

To prove if /star is an equivalence relation or partial order, we need to understand what they
are:

Equivalence relation is a relation which is reflexive, symmetric and transitive.

Partial order is a relation that is reflexive transitive and anti-symmetric.

From part a) to d) we have already found out that

If the relation is not reflexive, then it is neither equivalence relation nor partial order as
both need the relation to be reflexive.

Question 3

Show that for all integers 𝒏:

a) If 𝒅 is an integer such that 𝒅 | 𝒏 + 𝟗 𝒂𝒏𝒅 𝒅 | 𝒏𝟐 + 𝟕, then 𝒅 | 𝟖𝟖

Part a)

We are already given that:

𝑑 | 𝑛 + 9 𝑎𝑛𝑑 𝑑 | 𝑛( + 7

Using basic algebra, we can rewrite 𝑑 | 𝑛 + 9 as 𝑛 + 9 = 𝑘𝑑, and by solving for n, we get:

𝑛 = 𝑘𝑑 − 9

Substituting 𝑛 = 𝑘𝑑 − 9 into 𝑛( + 7:

𝑛( + 7 = (𝑘𝑑 − 9 )( + 7

𝑛( + 7 = (𝑘 ( 𝑑 ( − 18𝑘𝑑 + 81 ) + 7

𝑛( + 7 = 𝑘 ( 𝑑 ( − 18𝑘𝑑 + 88

Since we know 𝑑 | 𝑛( + 7, we can also state that 𝑑 | (𝑘 ( 𝑑 ( − 18𝑘𝑑 + 88)

We can see that the first two terms in 𝑘 ( 𝑑 ( − 18𝑘𝑑 + 88 are divisible by d, and by using the
divisibility rule, we can also state that the third term 88 will also be divisible by 𝑑.
Part b)

As we have been told that n is a multiple of 88, we can write 𝑛 as:

𝑛 = 88𝑘, for some integer 𝑘

We should prove that 𝑛 + 9 and 𝑛( + 7 are coprime, which states that the greatest common
divisor of 𝑛 + 9 and 𝑛( + 7 is 1.

The next step is substituting 𝑛 = 88𝑘 into both the expressions:

Expression 1:

𝑛 + 9 = 88𝑘 + 9

Expression 2:

𝑛( + 7 = (88𝑘)( + 7

𝑛( + 7 = 7744𝑘 ( + 7

We know that 𝑑 | 7744𝑘 ( + 7 and 𝑑 | 88𝑘 + 9, let us assume that the common divisor d is
greater than 1. In the above part (a), we have already proved that 88 is divisible by d, which
means that 𝑑 is one of the divisors of 88.

The divisors of 88 are: 1,2,4,8,11,22,44,88.

We have already seen that d divides both 88𝑘 + 9 and 88, which states that:

88𝑘 + 9 ≡ 0 (𝑚𝑜𝑑 𝑑)

By rearranging the above equation, we get:

9 ≡ −88𝑘 (𝑚𝑜𝑑 𝑑)

We know that 88k is divisible d, because 𝑑 | 88, but since 9 is not divisible by any other
divisor of 88 (1,2,4,8,11,22,44,88) except 1, the only possible divisor would be 1, therefore
𝑑 = 1.

Since the only common divisor of 𝒏 + 𝟗 and 𝒏𝟐 + 𝟕 is 1, we can therefore conclude that
𝒏 + 𝟗 and 𝒏𝟐 + 𝟕 are coprime.