# Help with proof set A= set B

• October 10th 2012, 01:22 PM
Ben91
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!!!
• October 10th 2012, 02:30 PM
Plato
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.

$2^k$ has a last digit of eight if $k\equiv_4 3$ (mod 4)
• October 10th 2012, 03:10 PM
johnsomeone
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.
• October 10th 2012, 03:55 PM
Plato
Re: Help with proof set A= set B
Suppose that $k\in\mathbb{N}$.

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