Number Theory Assignment: Problems on GCD, Congruences, and Proofs

This document presents the solutions to a number theory assignment. The solutions cover several key concepts, including the calculation of the greatest common divisor (GCD) using the Euclidean algorithm for numbers such as 7700 and 2233, and 357 and 629. It also demonstrates the application of the Euclidean algorithm to find integers s and t that satisfy the equation 357s + 629t = gcd(357, 629). Furthermore, the assignment includes proofs related to number theory principles, such as demonstrating that if a divides c, b divides c, and the GCD of a and b is 1, then the product of a and b divides c, and that if the GCD of a and b is 1, then the GCD of a+b and ab is 1. The solutions also provide a step-by-step approach to solve linear congruences, for example, 221x ≡ 65 (mod 429) and 35x ≡ 15 (mod 182). Lastly, it includes analysis of error detection schemes, such as those used for bank account numbers and ISBN codes, to identify errors in transmission or transposition of digits. The assignment is designed to test and enhance the student's comprehension of foundational number theory principles and problem-solving skills.

Running head: THEORY OF NUMBERS
THEORY OF NUMBERS
Name of the Student
Name of the University
Author Note

1THEORY OF NUMBERS
Answer to Question No. 1
Using the Euclidean algorithm,
7700 = 3*2233 + 1001
2233 = 2*1001 + 231
1001 = 4*231 + 77
231 = 3*77
So gcd(7700, 2233) = 77.
Answer to Question No. 2
Using the Euclidean algorithm,
629 = 1*357 + 272
357 = 1*272 + 85
272 = 3*85 + 17
85 = 5*17
So, gcd(357, 629) = 17. Moreover,
17 = 272 – 3*85
= 272 – 3(357 – 1*272)
= 4*272 – 3*357

2THEORY OF NUMBERS
= 4(629 – 1*357) – 3*357
= 4*629 – 7*357
= -7*357 + 4*629
Therefore, s = -7 and t = 4.
Answer to Question No. 3
If gcd(a,b) = 1,
then there exist integers s and t such that
as + bt = 1.
Therefore,
cas + cbt = c.
Now since a|c and b|c,
there exist integers m and n such that
c = ma and c = nb.
Therefore,
nbas + mabt = c.
Since ab divides the entire left hand side, it must also divide the right hand side.
Therefore, ab|c.

3THEORY OF NUMBERS
Answer to Question No. 4
Given gcd(a, b)=1,
and from Bézout's identity we have
gcd(a, b) = 1 ⟺ ∃x,y : ax + by = 1 for integer x and y.
1 = ax + by = ax + bx – bx + by = (a + b)x + b(y − x),
Therefore,
gcd(a + b, b) = 1
Again, gcd(a + b, a) = 1
because (a + b)y + a(x − y) = 1
1 = ((a + b)x + b(y − x)) ((a + b)y + a(x − y))
= (a + b)(a + b)xy + (a + b)a(x − y) + (a + b)b(y − x)y + ab(y − x)(x − y)
= (a + b)[(a + b)xy + a(x − y) + b(y − x)] + ab[(y − x)(x − y)]
So gcd(a+ b, ab) = 1
Answer to Question No. 5
a) 221x ≡ 65 (mod 429)
We have to first calculate the gcd (221, 429).
429 = 1*221 + 208

4THEORY OF NUMBERS
221 = 1*208 + 13
208 = 16*13
Therefore,
gcd (221, 429) = 13
Since gcd (221, 429) = 13, we can simplify the congruence by dividing by 13 to obtain,
17x ≡ 5 (mod 33)
Now it have to be noticed that,
gcd (17, 33) = 1.
Hence, solving the congruence can be continued by finding an inverse of 17 (mod 33).
33 = 17*1 + 16
17 = 16*1 + 1
Now,
1 = 17 + 16(-1)
1 = 17 + [33 + 17(-1)] (-1)
1 = 33(-1) + 17(2)
Therefore, we can use 2 as an inverse of 17 (mod 33). Thus, we can get:
(2)17x ≡ (2)5 (mod 33)

5THEORY OF NUMBERS
x ≡ 10 (mod 33)
So, one of the solutions is 10 (mod 33).
The other solutions are 10 + 33 = 43, 10 + (2)33 = 76, 10 + (3)33 = 109, 10 + (4)33 = 142, 10 +
(5)33 = 175, 10 + (6)33 = 208, 10 + (7)33 = 241, 10 + (8)33 = 274, 10 + (9)33 = 307, 10 +
(10)33 = 340, 10 + (11)33 = 373, 10 + (12)33 = 406, all (mod 429).
b) 35x ≡ 15 (mod 182)
Before we proceed to solve the given linear congruence, we do have to check whether this
congruence has any solution or not. To check that, we have to simplify the function and see
whether they are satisfying the equation that will be formed.
From,
35x ≡ 15 (mod 182)
We can simplify,
35x = 15 + 182k
35x – 182k = 15
7 (5x – 26k) = 15
The part, 5x – 26k will be an integer as x and k are integers. And in no condition the integral
multiple of 7 could be 15. Hence, this argument proves that this linear congruence has no
solution.

6THEORY OF NUMBERS
Answer to Question No. 6
a) According to the question the full number that is sent is 138639.
Now, let us suppose that the error number in place of the correct one is 138679. There is a error
in one of the digits in the number (but the error could be anywhere in the number including the
check number). Now it is to see that whether the technique that has been used can detect the
error in the number while being sent.
Correct number – 138639
Error number – 138679
The scheme that has been used to determine the check digit is,
For 138639,
1 + 3 + 8 + 6 + 3 + 9 ≡ 0 (mod 10)
which results into, 30 ≡ 0 (mod 10) and the congruence function has solutions.
Now, for the error number, 138679,
1 + 3 + 8 + 6 + 7 + 9 ≡ 0 (mod 10)
and results into, 34 ≡ 0 (mod 10) and the congruence function has no solutions. Hence, the error
in the number can be detected using this scheme.
b) It is to verify here that whether the given scheme in the previous question is valid for the
error in transposition of digits in the code.

7THEORY OF NUMBERS
The example code that has been considered for the verification is 138639 which has been sent as
136839 as error. If the above scheme is followed then for the correct code the determination of
the check digit will be,
1 + 3 + 8 + 6 + 3 + 9 ≡ 0 (mod 10)
Resulting,
30 ≡ 0 (mod 10).
This result has solutions.
On the other hand if the same scheme is being followed for the error code then the check digit
will determination will be,
1 + 3 + 6 + 8 + 3 + 9 ≡ 0 (mod 10)
Resulting,
30 ≡ 0 (mod 10)
which is same as the previous result. Hence it is verified that the above scheme cannot detect
errors formed due to transposition of digits in the code.
c) A 10 digit ISBN code taken for the example is 0-669-19496-4
Let the digits of the ISBN code be denoted as d10d9d8d7d6d5d4d3d2d1
And the incorrect transmission of the code is being sent as 0-669-91496-4 (adjacent transposition
error)
Then the arrangement will be d10d9d8d7d5d6d4d3d2d1.

8THEORY OF NUMBERS
The scheme that is followed for the error detection is,
10d10 + 9d9 + 8d8 + 7d7 + 6d6 + 5d5 + 4d4 + 3d3 + 2d2 + 1d1 ≡ 0 (mod 11)
For the correct code,
10(0) + 9(6) + 8(6) + 7(9) + 6(1) + 5(9) + 4(4) + 3(9) + 2(6) + 1(4) ≡ 0 (mod 11)
= 275 ≡ 0 (mod 11) and it satisfies the given scheme.
For the incorrect code transmission,
10(0) + 9(6) + 8(6) + 7(9) + 6(9) + 5(1) + 4(4) + 3(9) + 2(6) + 1(4) ≡ 0 (mod 11)
= 283 ≡ 0 (mod 11) and it does not satisfy the given scheme.
Hence, the scheme that is being used to detect errors in the ISBN code is valid for the
transposition of digits, irrespective of adjacent or random. As the total summation will be
different, the final condition for the scheme will not be satisfied and the error will be detected.