Discrete Mathematics Assignment: Proofs, Number Theory, and GCD

This document provides a comprehensive solution to a Discrete Mathematics assignment. The assignment covers a range of topics including proving or disproving statements related to modular arithmetic and parity, such as whether the average of two numbers with the same modulus has the same parity. It also involves proofs by contradiction and contraposition, specifically demonstrating the irrationality of the reciprocal of an irrational number and proving a statement involving modular arithmetic. The solution further includes problems on number theory, such as finding the unique prime factorization of a given integer, determining the smallest integer to make a number a perfect cube, and calculating the least common multiple (LCM) of two numbers. Finally, the assignment utilizes the Euclidean algorithm to determine the greatest common divisor (GCD) of two integers. The solutions are presented with clear steps and explanations.

DISCRETE MATHEMATICS
Q1.Prove or disprove each of the following statements:
(a)for all a,b belongs to z, if a congruent to b(mod 4)
Then we have to check whether the average of a and b has the same parity as a
For instance let us take a=4 b=2 then the average of a and b is (a+b)/2=6/2=3 which is not same as a
so the average of a and b does not have same parity as a that is this statement is disproved.
(b) There exists n such that 4n^2-12n+8 is prime
If we take n=1 then 4n^2-12n+8=4-12+8=0
If we take n=2 then 4n^2-12n+8=4(2)^2-12(2)+8=24-24=0
If we take n=3 then 4n^2-12n+8=4(3)^2-12(3)+8=36-36+8=8
If we taken=4 then 4n^2-12n+8=4(4)^2-12(4)+8=64-48+8=24
Now we can find that 0,,0,8,24 are not prime’
So the statement is disproved.
(c) ∀a, b ∈ Z, if 36a = 28b, then 7|a.
If 36a=28b which implies 12a=7b
If a=14 then 7 divides a.
(d) for all n belongs to z+ check whether ( 4n^2+1)/n^2 =5
If we take n=1 and n=2 we are not getting 5 as the answer.
So the statement is disproved.
(e ) for all n belongs to z+ check whether (4n^2+1)/4=5
If we check for instance n=1 we get the value as 5.
If we take n=2 then we are getting 17/4
So the statement is disproved
(2)The reciprocal of a nonzero real number x is 1 x . Prove the following statement using a proof by
contradiction. The reciprocal of every irrational number is irrational.
Proof:
Let x be a irrational number.suppose 1/x is rational then 1/x=a/b where a and b are integers a not
equal to 0 and since 0 is a rational number b not equal to 0
X=1/1/x=1/a/b=b/a where b and a are integers and a not equal to 0
[Type text]

Therefore x is rational
This is a contradiction so x is irrational .
Therefore 1/x is irrational.
(3) Prove the following statement using a proof by contraposition. ∀a, b, c ∈ Z, if ab + ac ≡ 3 (mod
6) then b not congruent to c (mod 6)
Solution if we take a=1,b=2 and c=1
Then ab+ac=2+1=3
b not congruent to c(mod 6) implies 2 not equal to 1(mod 6) =2-1 =1 is not divisible by 6
so the statement is proved
4(a) (a) Determine the unique prime factorisation of 138, 411 in standard form.
138,411 =(3^2)(7^2)(13^2)
(b) Find the smallest positive integer n such that 138, 411n = x^3 for some integer x.
If we take n=1 then 138,411(1)=x^3
So x^3=(51.7277437)^3
So n=1 is the smallest integer
(c ) Find the lcm(138411, 49).
138,411 =(3^2)(7^2)(13^2)
49 =7^2
So the lcm(138411,49) =(7^2) (3^2)(13*2)=138411
(5) ) Use the Euclidean algorithm to determine gcd(399, 3150).
Dividend = DivisorxQuotient +Remainder
3150=399x7+357
399=1x357+42
357=8x42+21
42=2x21+0
So the GCD(3150,399) =21
3150 =399x
[Type text]

399=1X357+42
357=8x42+21
42 2X21+0
So the GCD(3150,399) is 21.
[Type text]