Mathematics
: asked on mwangikabuya

08.12.2022 the following question

1A. Prove that GCD(a, a+2) = 1 if a is odd, and GCD(a, a+2) = 2 if a is even

1B. Show that if a≡b(mod n) and if b≡c(mod n), then a≡c(mod n)

1C. Simplify the following congruences:

15x≡9 (mod 25)

6x≡3 (mod 9)

14x≡42 (mod 50)

1D. Describe the general solution for x and y, if it exists: 35x+47y=1

Request clarification:

Expert:

We answer only one question at a time. You decide

User:

Hello, this is one question with 4 parts. If not possible to answer all please answer part C and DExpert:

I can solve Only D.. do you want it

User:

Okay then, is there another part you can also solve? If yes, please assist also 6

08.12.2022, solved by verified expert

Unlock the full answer

1 students found this answer helpful

**Answer:**

**Step-by-step explanation:**

A)

If a = 1, then gcd(1, 3) = 1.

If a > 1, then lets execute a single step of the Euclidean algorithm:

gcd (a+2, a) = gcd(a, (a + 2) mod a)

[Here, "x mod y" denotes the remainder of division of x by y.]

Now, clearly, (a + 2) mod a = 2, since a > 2. (a is

odd, and a 1, so a has to be at least 3.)

So, we have

gcd(a+2, a) = gcd (a, 2).

Continuing with the Euclidean algorithm, we get

gcd(a, 2)= gcd (2, a mod 2).

We know that a is odd, i.e., a mod 2 = 1, and clearly gcd (2, 1) = 1.

D)

Studen helps you with homework in two ways: