practice problems pending from Q3

Q1. For any integer a, show the following:

(a) gcd(2a+1,9a+4)=1.
(b) gcd(5a+2,7a+3)=1.
(c) If a is odd, then gcd(3a,3a+2)=1. 

S1.
(a) Using Euclid algorithm:
(2a+1,9a+4) = (2a+1,a) = (1,a) = 1
(b)
(5a+2,7a+3) = (5a+2,2a+1) = (a,2a+1) = (a,1) = 1
(c)
(3a,3a+2) = (3a,2)
Since 3a is odd => gcd = 1

Q2. If  a∣bc, then show that a∣ gcd(a,b) gcd(a,c)
S2.
Using Bezout's identity:
gcd(a,b) = d1 = m1a + m2b
gcd(a,c) = d2 = n1a + n2c
d1.d2 = m1.n1.a^2 + m1.n2.ac + n1m2ab + m2n2bc
We need to show that d1d2 = ak.
Each term in d1.d2 is div by a except m2n2bc but we know that bc is div by a.
H.P.

Q3. Use the Euclidean Algorithm to obtain integers x and y s.t.

(a)  gcd(56,72)=56x+72y.
(b) gcd(24,138)=24x+138y.
(c) gcd(119,272)=119x+272y.
(d) gcd(1769,2378)=1769x+2378y.

S3.
(a) (56,72) = (56,72-56.1=16) = (56-16*3 = 8,16) = 8
8 = 56-(72 - 56.1)*3  = 56*4 - 3*72 = 224-216

(b) gcd(24,138)

= 24,138-24*5 = 24,18 = 24-18,18 = 6,18 = 6
(138-24*5)*(-1) + 24 = 24*6 - 138*1 = 144-138 = 6 

(c) 

(119,272) = a,b
= (119,272-119*2)
= 119,34
= 119-34*3,34 = 17,34 = 17

34 = 272-119*2  = b-2a
17 = 119-34*3 = a-3(b-2a) = 7a-3b

(d)
(1769, 2378)
= 1769,2378-1769
= 1769,609
= 1769-2*609
= 551,609
= 551,609-551
=551,58
= 551-58*9,58
= 29,58
= 29

So
(2378 - 1769) = 609 = a-b
1769-2*609 = 551 = b-2*(a-b) = 3b-2a
609-551 = 58 = a-b-3b+2a  = 3a-4b
551-58*9 = 29 = 3b-2a -9*(3a-4b) = -29a + 39b = answer

Q4. Let a,b,c be integers, no two of which are zero, and d = gcd(a,b,c). Show that d=gcd(gcd(a,b),c)=gcd(a,gcd(b,c))=gcd(gcd(a,c),b).
S4.

Let a,b,c = k1.d, k2.d, k3.d

=> gcd(a,b) = d * gcd(k1,k2)

And

gcd( gcd(a,b), c) = gcd ( d* gcd(k1,k2), k3.d) = d* gcd(gcd(k1,k2), k3)

So we need to show that:

gcd(gcd(k1,k2), k3) = 1

Let's prove by contradiction:

Let gcd(gcd(k1k2), k3) = p where p > 1

Then

k1 = m1.p

k2 = m2.p

k3 = m3.p

=> a = m1.p.d, b = m2.p.d, c = m3.p.d

In that case

gcd(a,b,c) = p.d

Hence contradiction.

Hence proved.

Similarly the other two.

Q5.

Fermat Numbers: The integers Fn = 2^(2^n) + 1, n>= 0, are called Fermat Numbers. 

F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537 are primes, but F5 = 4,294,967,297 is divisible by 641. Primes among Fermat numbers are called Fermat primes. Gauss (1801) proved that if m is a Fermat prime then a regular polygon of m sides can be constructed just using ruler and compass. It is not known whether there are infinitely many Fermat primes. In fact,  F0, F1,F2,F3,F4 are the only known Fermat primes. It is known that Fn​ is composite if 5≤n≤32.

Prove that:

(i) Fn - 2 = F0.F1...F_{n-1} ,n≥1.

(ii) Any two Fermat numbers are relatively prime.

S5.
(i)
Pr. th. 2^(2^n) + 1 - 2 = (2^(2^0) +1). (2^(2^1) +1). ... (2^(2^{n-1}) +1).
(2^(2^0) +1) = (2^(2^0) -1). (2^(2^0) +1) (essentially we are multiplying by 1).
= 2^(2^1) - 1
Similarly:
[2^(2^1) - 1] * [2^(2^1) + 1] = 2^(2^2) - 1
So we can keep reducing the RHS and eventually we get 2^(2^n) - 1.
H.P.

(ii)
Let n > m.
Proof by contradiction.
gcd(Fm,Fn) = d where d > 1
Fn - 2 = F0.F1..Fm..F_{n-1}
So Fm divides Fn - 2.
Since d divides Fm, it should also divide Fn - 2.
Since d divides both Fn, Fn - 2, it should divide their difference as well.
So d divides 2.
d can be 1 or 2.
But every Fermat number is odd.
=> d = 1
H.P.

Q6.

The numbers in the sequence 101,104,109,116,… are of the form a_n = 100 + n^2 n=1,2,3,..
For each n, let d_n be gcd(a_n,a_{n+1}). Find the maximum value of d_n as n ranges through the positive integers.
S6.
(100 + n^2, 100 + (n+1)^2) = 100 + n^2, 2n + 1
2n+1 is odd, so we can multiply the other number with 2 and gcd won't change.
= 200 + 2n^2, 2n+1
Multiply the right one by 2 and subtract:
= 200 + 2n^2 - 2n^2 - n, 2n+1
= 200 - n, 2n + 1

Since gcd(-a,b) = gcd(a,b)
= n - 200, 2n + 1
Again mult by 2
= 2n - 400, 2n + 1
= 2n - 400, 2n + 1 - 2n + 400
= 2n - 400, 401

Since d_n must divide 401 it has to be 1,401 since 401 is prime(check with 2,3,5,7,11,13,17,19).
To check whether it is achievable set 2n+1 = 401 => n = 200
a_200 = 100 + 200^2 = 40100
a_201 = 100 + 201^2 = 40501 = 40100 + 00401 = 401 * 101
So it is achievable.

Q7.
Prove that the fraction
(21n+4)/(14n+3)

is irreducible for every natural number 'n'.

S7.
We need to show that gcd(21n+4,14n+3) = 1
Let's use Euclid algo.

To find gcd using Euclid, we keep taking remainder while dividing larger number with the smaller. When the remainder is 0 we take the divisor as answer.

gcd(21n+4,14n+3) = gcd(7n+1,14n+3) = gcd(7n+1,1) = 1