Results 1 to 4 of 4

Math Help - Help with proof set A= set B

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    3

    Unhappy Help with proof set A= set B

    So here's the question :

    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!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,707
    Thanks
    1637
    Awards
    1

    Re: Help with proof set A= set B

    Quote Originally Posted by Ben91 View Post
    So here's the question :
    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)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    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.
    Last edited by johnsomeone; October 10th 2012 at 02:15 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,707
    Thanks
    1637
    Awards
    1

    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)~.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  2. Replies: 0
    Last Post: June 29th 2010, 08:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum