MA161 Assignment 2 Question 1 (A) Prime Number Composite Number

MA161
Assignment 2
Question 1 (a)
Prime Number
A prime number is a number that is only Divisible by 1 and the number itself.
Composite Number
A composite number is a number that can be divided by 1 and other numbers.
E.g. 6
6/2 =3
6/3 =2
6/6 =1
Thus 6 is a composite number and has factors of 1,2,3,6.
Since 512, is only divisible by 1, thus, 512 is prime.
Question 1(b)
52100 / 2 = 26050
26050 / 2 = 13025
13025 / 5 = 2605
2605 / 5 = 521
521 / 521 = 1
Question 2(a)
Prove that if n is an integer, then n2 ≡ 0 or 1(mod 4).

Proof. Let n ∈ Z. Then either n is even or n is odd.
n2 ≡ 0(mod 4).
STEP1:
Assume n is even If m is even, then there exists k ∈ Z such that n = 2k.
STEP2:
Then n2 = 4k2, so 4| n2 and hence n2 ≡ 0(mod 4).
Or
n2 ≡ 1(mod 4).
Assume n is odd If n is odd, then there exists k ∈ Z such that n = 2k + 1.

Then n2 = 4k2 + 4k + 1, so n2 − 1 = 4(k2 + k). Thus n2≡ 1(mod 4).
Thus if n is an integer, then n2 ≡ 0(mod 4) or n2≡ 1(mod 4).

Question 2 (b)
Prove by mathematical induction that n2 − 5n + 3 > 0 whenever n is an integer greater
than 4.
Proof: step 1 n=5
= n2 − 5n + 3 > 0
= (52) + 5(5) + 3 >= 0
= 53 > 0
Step2: n = k
ASSUME P(k) is true k2 – 5k + 3 > 0 where n>4 = (k-2) (k-3)>=0
Step 3: n=K+1
= k+12 – 5(k+1) + 3 > 0
Now let n be an arbitrary integer satisfying n≥4, and suppose that n2 − 5n + 3 > 0

Then
(k+1)2 – 5(k+1) + 3 = ((k+1)2 -5(k+1)+3 >=0
= [(k+1)-5][(k+1) + 3] >=0
For all values of k+1, k+1 is greater than or equal to 5
Since the least value of k is 4 so the least value of k+1 is 4
So the product of [(k+1)-2] [[ k+1]-3] >= 0
Therefore, by mathematical induction, n2 − 5n + 3 > 0 is true
for every integer n>4.
Question 3
Octal expansion of 1100110011002.
Convert every 3 binary digits to octal

110| 011| 001| 100
6 | 3| 1| 4
6314.
Thus, 110011001100 to octal conversion is equal to 6314
Hexadecimal expansion of 1100110011002.
1100| 1100| 1100

12 |12 | 12
CCC
Thus, 110011001100 to Hexadecimal conversion is equal to CCC.
Question 4 (a)
GCD (178, 67) using Euclidean Algorithm
178 ÷ 67 = 2 + 44
67 ÷ 44 = 1+ 23
44 ÷ 23 = 1+21
23 ÷ 21 = 1+2
2 ÷ 1 = 2+0
Thus, the Greatest Common Divisor of (178, 67) is 1 using Euclidean

Algorithm.
Question 4 (b)
Express GCD (178, 67) as a Linear combination
1 = 1 × 21 – 10 × 2
1 = 1 × 21 – 10 × (23 – 1 × 21)
1 = -10 × 23 + 11 × 21
1 = -10 × 23 + 11 × (44 – 1 × 23)
1 = 11 × 44 – 21 × 23
1 = 11 × 44 – 21 × (67 – 1 × 44)
1 = -21 × 67 + 32 × 44
1 = -21 × 67 + 32 × (178 – 2 × 67)
1 = 32 × 178 – 85 × 67
178 × x + 67 × y = 1
Has a solution of (x, y)= (32, -85)
Question 4 (c)
Find the Inverse of 178 modulo 67.
Gcd=1
178/67 = 2 R 44
67/44 = 1 R 23
178-2(67)
67-1(44)
178-2(67-1(44) = 32 is the inverse of 178 mod 67
Question 4 (d)
Find an inverse of 67 modulo 178
Gcd = 1
67-1(178-2(67) = 93 is the inverse of 178 mod 67
Question 4 (e)
178 ≡ 53(mod 67)
First calculate gcd of 178 mod 67 = 1
178-2(67-1(44) = 32
32.178 ≡ 32.53 (mod 67)

= 21 is linear congruence of 178 ≡ 53(mod 67).
Question 5 (a)
recursive algorithm for finding the sum of the first n even positive integers.
procedure even_sum (n: positive integer)
if n = 1 then return 0
else return even_sum (n/2 x (a + Tn))

Question 5 (b)
Input parameters & values:
The number series 2, 4, 6, 8, 10.
The first term a = 2
The common difference d = 2
Total number of terms n = 5
Sum = n/2 x (a + Tn)
= 5/2 x (2 + 10)
= (5 x 12)/ 2
= 60/2
2 + 4 + 6 + 8 + 10 = 30
Therefore, 30 is the sum of first 5 even numbers
Question 6(a)
On each place of the password we can place

26(lowercase letters)
26(uppercase letters)
10(digits)
4(special characters)
26+26+10+4 = 66 characters
(a)
For 6-digit password: 667
667 +668 +669 +6610 = 1.59x1018 different passwords available

Question 6(b)
A password has no special characters means on each place we can put 66 - 4 = 62
characters.
66^7+66^8+66^9+66^10 - 62^7-62^8-62^9-62^10 =
1.59x1018 – 8.53 x 1017
= 7.37 x 1017 different passwords with at least one occurrence of at least one special
characters available
Question 6(c)
It will take 7.37 x 1017 microseconds
7.37 x 1017 / 1000∗60∗60∗24∗365 = 23,370,1117 years
(23,370,1118 years if take leap years into account). All the calculations have some
inaccuracy.

MA161 Assignment 2 Question 1 (A) Prime Number Composite Number

Uploaded by

Copyright:

Available Formats

MA161 Assignment 2 Question 1 (A) Prime Number Composite Number

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

MA161 Assignment 2 Question 1 (A) Prime Number Composite Number

Uploaded by

Copyright:

Available Formats

MA161

Prove that if n is an integer, then n2 ≡ 0 or 1(mod 4).

Assume n is odd If n is odd, then there exists k ∈ Z such that n = 2k + 1.

Thus if n is an integer, then n2 ≡ 0(mod 4) or n2≡ 1(mod 4).

Proof: step 1 n=5

= k+12 – 5(k+1) + 3 > 0

Now let n be an arbitrary integer satisfying n≥4, and suppose that n2 − 5n + 3 > 0

Octal expansion of 1100110011002.

Convert every 3 binary digits to octal

1100| 1100| 1100

Thus, 110011001100 to Hexadecimal conversion is equal to CCC.

GCD (178, 67) using Euclidean Algorithm

Thus, the Greatest Common Divisor of (178, 67) is 1 using Euclidean

Express GCD (178, 67) as a Linear combination

Find the Inverse of 178 modulo 67.

178-2(67-1(44) = 32 is the inverse of 178 mod 67

Find an inverse of 67 modulo 178

67-1(178-2(67) = 93 is the inverse of 178 mod 67

178 ≡ 53(mod 67)

First calculate gcd of 178 mod 67 = 1

32.178 ≡ 32.53 (mod 67)

procedure even_sum (n: positive integer)

if n = 1 then return 0

else return even_sum (n/2 x (a + Tn))

The number series 2, 4, 6, 8, 10.

The first term a = 2

The common difference d = 2

Total number of terms n = 5

Sum = n/2 x (a + Tn)

Therefore, 30 is the sum of first 5 even numbers

On each place of the password we can place

667 +668 +669 +6610 = 1.59x1018 different passwords available

It will take 7.37 x 1017 microseconds

7.37 x 1017 / 1000∗60∗60∗24∗365 = 23,370,1117 years

You might also like