Help with proof set A= set B

So here's the question(Crying) :

Let

A = {n ∈ N : the last digit of 2^n is 8},

B = {n ∈ N : n+1 is divisible by 4}.

Show that A = B.

Now i understand what this question is saying and i understand that A does in fact = B. But i have no idea how to prove this... Any hints or help would be much appreciated.

Thank you!!!

Re: Help with proof set A= set B

Quote:

Originally Posted by

**Ben91** So here's the question(Crying) :

Let

A = {n ∈ N : the last digit of 2^n is 8},

B = {n ∈ N : n+1 is divisible by 4}.

Show that A = B.

Now i understand what this question is saying and i understand that A does in fact = B. But i have no idea how to prove this... Any hints or help would be much appreciated.

$\displaystyle 2^k$ has a last digit of eight if $\displaystyle k\equiv_4 3$ (mod 4)

Re: Help with proof set A= set B

Let n in A.

Then the last digit of 2^n is 8.

Note by direct calculation that n isn't 1 or 2, so n>=3.

That means that 2^n = 10k + 8 for some non-negative integer k.

Which means that 2^(n-1) = 5K + 4.

Which means that 2^(n-1) = 4 = 2^2 mod 5.

Since the gcd(5, 2) = 1, it follows that 2 has a multiplicative inverse mod 5 (It's 3, since (2)(3) = 1 mod 5).

Multiply both sides by the mutiplicative inverse of 2 (i.e. 3) twice.

Get: 2^(n-3) = 1 mod 5

Sideline:

What's the smallest positive power of 2 that gives you 1 mod 5? That will be the multiplicative order of 2 mod 5.

The powers are: 2^1=2, 2^2=4, 2^3=8=3, 2^4=16=1.

Thus 2^4 = 1 mod 5 and the mod-5-multiplicative-order of 2 is 4.

Thus 2^a = 1 mod 5 if and only if 4 divides a.

Back to the problem:

Had proven that, if n in A, then 2^(n-3) = 1 mod 5.

But that implies that 4 divides (n-3).

Hence 4 divides ((n-3) + 4).

Hence 4 divides (n+1).

Therefore n is in B.

That proves that A is a subset of B.

I'll leave it to you to show that B is a subset of A, and hence complete the proof that A = B.

Re: Help with proof set A= set B

Suppose that $\displaystyle k\in\mathbb{N}$.

$\displaystyle k \equiv _4 3\text{ if and only if }4|(k+1)~.$