MATH1061/7861 Assignment 2, Semester 2/2018: Number Theory Problems

This document provides solutions to MATH1061/7861 Assignment 2, focusing on fundamental concepts in number theory. The assignment covers topics such as finding the greatest common divisor (GCD) and least common multiple (LCM) using unique prime factorization and the Euclidean algorithm. It also includes problems related to proving or disproving mathematical statements involving real, irrational, and integer numbers, with an emphasis on counterexamples and proof techniques. Furthermore, the assignment explores divisibility rules, remainders of perfect squares, and mathematical induction to prove a given expression. The solutions are detailed and provide step-by-step explanations for each problem.

MATH 1061/7861
Assignment 2
Student Name
[Pick the date]

Question 1
(a) Method: Unique prime factorisation
 gcd ( 270 , 924 )∧lcm ( 270 , 924 )
2 270
5 135
3 27
3 9
3
2 924
2 462
11 231
7 21
3
270=2∗5∗33
924=22∗11∗7∗3
gcd ( 270 , 924 )=21∗50∗31∗110∗70=2∗3=6
lcm ( 270 , 924 ) =22∗5∗11∗7∗33=41580
(b) Method: Euclidean algorithm
gcd ( 132153 , 4263 )
4263 132153 31
132153
0
132153=4263∗31+ 0
gcd ( 132153 , 4263 )=4263
1

Question 2
(a)The given statement is false as can be established from the following counterexample.
Let x = 2.5, y =-2.5
L.H.S. = I2.5-2.5I = 0
R.H.S. = 2.5 + 2.5 = 5
Clearly, the two are not equal and hence the given statement is false.
(b)The given statement is false as can be established from the following counterexample.
Let x = 2.5, y =-2
L.H.S. = I2.5-2I = 0.5
R.H.S. = 2.5 + 2 =4.5
Clearly, the two are not equal and hence the given statement is false.
(c) “For all irrational numbers x, the number 10x+3 is also termed as irrational.”
Let assume 10x+3 is rational and hence,
10 x+ 3= p
q
Where,
p , q ∈ z' ∧q ≠ 0
10 x=( p
q )−3
10 qx= p−3 q
x= 1
10
( p−3 q )
q
2

Here, x comes out to be rational for the contraction in the assumption that 10+x is rational and
hence, it is proved that 10+x would be irrational for being x as irrational.
(d) For all a , b , d ∈ z' if d |ab , thend|a∨d∨b
Let’s assume
d∨a
Hence, the greatest common divisor of a and d would be equal, which mean d' ( ≥ 1 )
gcd ( a , d )=d' d' <a
a x0 +d y0=d' d' < d
It is because the gcd is always represented as a linear combination. It can also be understood with
the help of the example shown below.
G |4∗3∨6|12
But
6∨4∧6∨3
Also, one needs to consider d to be the prime hence,
d' =1
gcd ( a , d )=1
a x0 +d y0=d'
a x0 +d y0=1
b (a x0+ d y0 )=b
ab x0 +db y0 =b
Thus,
d |ab∧d |db y0
So,
d∨ab x0+ db y0
3

Hence,
d∨b
(e) For all a , b , d ∈ z' if d |a+b ,∧d|a , thend ∨b
Based on the above conditions the following equations can be derived.
( a+b ) =d k 1
a=d k2
Thus,
( a+b )−a=d k 1−d k2
a+ b−a=d k 1−d k2
b=d k1−d k 2
b=d ( k ¿¿ 1−k2 )¿
d
b
Proved
Question 3
(a) The infinite perfect squares are shown below.
1 , 4 , 9 , 16 , 25 ,36 , 49 … … … … … …. .
It is apparent that there are only four possible remainders which the perfect square is divided by
7.
Hence,
When 1 is divided by 7 then the remainder would be 1.
When 4 is divided by 7 then the remainder would be 4.
When 9 is divided by 7 then the remainder would be 2.
4

When 25 is divided by 7 then the remainder would be 2.
When 36 is divided by 7 then the remainder would be 1.
When 49 is divided by 7 then the remainder would be 0.
Therefore, the remainder (r) would be 0, 1, 2, 4.
(b) The case when 2kis divided by 7 then,
20=1 , r=1
21=2 , r=2
22=4 , r=4
23=8 ,r =1
24 =16 , r=2
25=32 , r=4
26=64 , r=1
Therefore, the remainders (r) would be 1, 2, 4.
(c) The following conclusion can be drawn based on the above two parts.
n2 results remainder 0 ,1 , 2, 4
2m results remainder 1 , 2 , 4
Hence, if one will add the above two 2m +n2 then any of the two remainders, then there would be
no zero as shown below.
0+1 , 0+2 , 0+4
1+1 ,1+2 , 1+4
2+1 , 2+ 2, 2+4
4 +1 , 4+ 2, 4 + 4
Thus, it can be seen from the above that we will never get a zero or multiple of 7 and thereby, 7
does not divide 2m +n2i.e.
5

2m +n2 ≠ 0 ( Mod 7 )
Thus, no integer solution is exists for this.
Question 4
(a) The general term of the sequence is given by (-2)k where k≥0
Hence, first term = (-2)0 = 1
Second term = (-2)1 = -2
Third term = (-2)2 = 4
Fourth term = (-2)3 = -8
Hence, the first four terms of the given sequence are 1,-2,4 and -8.
(b) Mathematical expression needs to be proved through induction method is shown below.
1−3 ∑
k=0
n
(−2)k=(−2)n+1
Initial step: Let’s put n= 0 in the expression and prove that LHS and RHS are same.
Put n=0
1−3 ∑
k=0
0
(−2)k=(−2)0+1
1−3 (−2 )0 = (−2 )1
1−3 ( 1 ) =−2
−2=−2( Proved∧satisfied )
Inductive step: Assume there is n=m, which is a positive integer for which the expression is true
and hence, the second step in the induction in that it is also held to be true for n=m+1.
Put n= m (Positive integer). Let us assume that for n= m, the following equation is satisfied
1−3 ∑
k=0
m
(−2)k=(−2)m+1
6

Let’s put n= m+1 (Positive integer)
LHS=1−3∑
k=0
m+1
(−2)k
¿ 1−3 ∑
k=0
m
(−2 )k−3 (−2 )m +1
¿ (−2 )m +1−3 (−2 )m +1
¿−2∗( −2 ) m+1
RHS= ( −2 ) ( m+1 ) +1= ( −2 ) m +2=−2∗( −2 ) m +1
Hence, it is true as LHS= RHS.
7