MHB Intersection of Sets A, B and C in ℤ

[fatineouahbi]

Let A,B,C be three sets such that :

A={x∈ ℤ / x=11k+8 , k∈ℤ}
B={x∈ ℤ / x=4k , k∈ℤ}
C={x∈ ℤ / x=11(4k+1) -3 , k∈ℤ }

Prove A⋂B = C

I started with this :
Let x be an arbitrary element of A⋂B
then ∃(k,k')∈ ℤ² such that x=11k+8 and x=4k'
then 11k+8 = 4k'
then 11(k+1)-3 = 4k'

I don't know where to go from this

 

[Euge]

Hi fatineouahbi,

Since $11k + 8 = 4k'$, then $11k = 4k' - 8$, or $11k = 4(k'-2)$. Hence, $4$ divides $11 k$. As $4$ and $11$ are relatively prime, $4$ divides $k$. So $k = 4u$ for some integer $u$. Now we have $x = 11k + 8 = 11(4u) + 8 = 11(4u + 1) - 3\in C$, showing that $A\cap B \subset C$.

To prove $A\cap B \subset C$, let $x\in C$. Then $x = 11(4k + 1) - 3$ for some integer $k$. Since $11(4k + 1) - 3 = 11(4k) + 8$, then $x\in A$. As $11(4k + 1) - 3 = 11(4k) + 8 = 4(11k) + 4(2) = 4(11k + 2)$, we have $x\in B$. Therefore, $x\in A\cap B$. Consequently, $C\subset A\cap B$.

 

[fatineouahbi]

Thank you !

 

[HallsofIvy]

Another way: 11k+ 8= 4k' is the same as 4k'- 11k= 8, a "linear Diophantine equation" which can be solved using "Euclid's algorithm":

4 divides into 11 twice with remainder 3: 11- 2(4)= 3.
3 divides into 4 once with remainder 1: 4- 3= 1.
Replace that "3" with 11- 2(4). 4- (11- 2(4))= 3(4)- 1(11)= 1.
Multiplying by 8, 24(4)- 8(11)= 8.

So one solution is k'= 24, k= 8. In fact, all values k'= 24+ 11n, k= 8+ 4n, for n any integer, is also a solution:
4(24+ 11n)- 11(8+ 4n)= 96+ 44n- 88- 44n= 96- 88= 8.

Members of the set are of the form x= 4k'= 96+ 44n for n any integer.