Additional Problem Set 8 Solutions
Additional Problem Set 8 Solutions
1
.
1
.1
.27
10
11011
2
1
.2
.1111111
2
127
10
1
.3
.101
10
1100101
2
2
.20
3
.We will show different arguments
3
.1
.This follows from the fact that there is a linear combination of a and a+1 that gives 1, namely (a+1) - (a)=1
3
.2
.Let d be a divisor of a.
If d is a divisor of a+1, then d divides (a+1) - a=1. (using that if d|n and d|m then d|n-m)
So d|1.
That is d = 1, or d=-1.
Thus the set of common divisors of a and a+1 is {-1,1}.
The largest of those numbers is 1.
If d is a divisor of a+1, then d divides (a+1) - a=1. (using that if d|n and d|m then d|n-m)
So d|1.
That is d = 1, or d=-1.
Thus the set of common divisors of a and a+1 is {-1,1}.
The largest of those numbers is 1.
3
.3
.COnsider using the Euclidean algorithm:
a+1 = a*1 + 1
a = 1*a + 0
So 1 = GCD(a,a+1)
a+1 = a*1 + 1
a = 1*a + 0
So 1 = GCD(a,a+1)
4
.
4
.1
.Note that if a is odd, then (a)-(a+2)=1 with and integers.If is even then and and
(a+1)
2
a-1
2
(a+1)
2
(a-1)
2
a
2|a
2|a+2
2=(a+2)-a
4
.2
.Alternatively note that a prime number p is such that if then only if , since . But only if is even.
p|a
p|a+2
p=2
p|(a+2)-a
2|a
a
4
.3
.Consider using the Euclidean algorithm:
a+2 = a*1 +2
Now we have two cases: 1) a is even 2) a is odd
1) a = 2k for some integer k, then
a = 2*k + 0
so GCD(a, a+2) = 2
2) a = 2k + 1 for some integer k, then
a = 2*k +1
2 = 1*2 + 0
so 1 = GCD(a,a+2)
a+2 = a*1 +2
Now we have two cases: 1) a is even 2) a is odd
1) a = 2k for some integer k, then
a = 2*k + 0
so GCD(a, a+2) = 2
2) a = 2k + 1 for some integer k, then
a = 2*k +1
2 = 1*2 + 0
so 1 = GCD(a,a+2)
5
.a≡b (mod n) if there is k∈ such that a = b +kn
b≡c (mod n) if there is j∈ such that b = c+jn
so a = c + jn + kn
so a = c + (j+k)n with (j+k)∈
so a≡c (mod n)
b≡c (mod n) if there is j∈ such that b = c+jn
so a = c + jn + kn
so a = c + (j+k)n with (j+k)∈
so a≡c (mod n)
6
.
6
.1
.No solutions
6
.2
.6x3
≡
9
2x1
≡
3
x≡2 (mod 3)
6
.3
.14x42
≡
50
7x21
≡
25
126x378
≡
25
x≡3 (mod 25)
7
.
7
.1
.47 = 35 + 12
35 = 12*2 +11
12 = 11 +1
1 = 12-11
1= 12 - (35-12*2)
1 = 12(1+2) -35 = 12 (3) -35
1 = (47-35)(3) -35
1 = 3(47) -4(35)
So the general form is
x= -4 + 47 k
y = 3 -35k
35 = 12*2 +11
12 = 11 +1
1 = 12-11
1= 12 - (35-12*2)
1 = 12(1+2) -35 = 12 (3) -35
1 = (47-35)(3) -35
1 = 3(47) -4(35)
So the general form is
x= -4 + 47 k
y = 3 -35k
7
.2
.35x + 47y =1
12 y1
y = 35k+3 for k∈
1 = (3+35k)(47) + x 35
1-3*47 -35*47k = 35x
-4 - 47k = x
So the general solution is
47y1
≡
35
12 y
≡
35
36y3
≡
35
y3
≡
35
y = 35k+3 for k∈
1 = (3+35k)(47) + x 35
1-3*47 -35*47k = 35x
-4 - 47k = x
So the general solution is
x=-4-47k
y=3+35k