2^(2^n) is congruent to 1 mod 3?

Maths and statistics discussion, revision, exam and homework help.

Announcements Posted on
Please change your TSR password 23-05-2013
Enter our travel-writing competition for the chance to win a Nikon 1 J3 camera 20-05-2013
IMPORTANT: You must wait until midnight (morning exams)/4.30AM (afternoon exams) to discuss Edexcel exams and until 1pm/6pm the following day for STEP and IB exams. Please read before posting, including for rules for practical and oral exams. 28-04-2013
Search Thread
Advanced Search
Sign in to Reply
  1. obbsidian's Avatar
    1 31-03-2012  14:45
    • Exalted Member
    • Location: High Wycombe
    • Posts: 281
    2^(2^n) is congruent to 1 mod 3?
    Can anyone see why 2^(2^n) is congruent to 1 mod 3?

    Thanks.
  2. TenOfThem's Avatar
    2 31-03-2012  14:50
    • TSR Royalty
    Re: 2^(2^n) is congruent to 1 mod 3?
    some rubbish by me


    OMG ... Sorry ... dim as anything
    Last edited by TenOfThem; 31-03-2012 at 15:03.
    Post rating:
    1
  3. TheMagicMan's Avatar
    3 31-03-2012  14:54
    • Overlord in Training
    • Posts: 2,940
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by obbsidian)
    Can anyone see why 2^(2^n) is congruent to 1 mod 3?

    Thanks.
    You can induct as well although the easiest way is direct modular arithmetic
  4. TheMagicMan's Avatar
    4 31-03-2012  14:55
    • Overlord in Training
    • Posts: 2,940
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by TenOfThem)
    because 2^2 = 4

    4^n = (3+1)^n = 3^n + 3^{n-1}1 + ......... + 1

    All the bits apart from the 1 have 3 to some power so are 0 [mod3]
    You cold just invoke that if a\equiv b (mod m) then a^n\equiv b^n (mod m) (not that it makes any difference)
  5. obbsidian's Avatar
    5 31-03-2012  14:55
    • Exalted Member
    • Location: High Wycombe
    • Posts: 281
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by TenOfThem)
    because 2^2 = 4

    4^n = (3+1)^n = 3^n + 3^{n-1}1 + ......... + 1

    All the bits apart from the 1 have 3 to some power so are 0 [mod3]
    I don't follow... are you saying 2^(2^n)=4^n? This is clearly not true, 4^n=2^(2n) not 2^(2^n).
  6. nuodai's Avatar
    6 31-03-2012  14:56
    • PS Helper
    • TSR Legend
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by TenOfThem)
    because 2^2 = 4

    4^n = (3+1)^n = 3^n + 3^{n-1}1 + ......... + 1

    All the bits apart from the 1 have 3 to some power so are 0 [mod3]
    That's 2^{2n} and not 2^{2^n}. (Edit: Also that's not the binomial theorem!) (Edit 2: That said, it'd be right if you used the binomial theorem correctly, and it would prove the OP's result since 2^{2^n}=4^{2^{n-1}}.)

    @OP: You can prove it by induction, using the fact that 2^{2^n}-1 = (2^{2^{n-1}})^2 - 1 = (2^{2^{n-1}}-1)(2^{2^{n-1}} + 1)
    Last edited by nuodai; 31-03-2012 at 15:00.
  7. obbsidian's Avatar
    7 31-03-2012  14:59
    • Exalted Member
    • Location: High Wycombe
    • Posts: 281
    Re: 2^(2^n) is congruent to 1 mod 3?
    Ive just tried induction as per magic mans suggestion and it comes out easy peasy. Thanks.
  8. deejayy's Avatar
    8 31-03-2012  15:02
    • Adored and Respected Member
    • Location: Melbourne
    • Posts: 505
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by nuodai)
    That's 2^{2n} and not 2^{2^n}. (Edit: Also that's not the binomial theorem!) (Edit 2: That said, it'd be right if you used the binomial theorem correctly, and it would prove the OP's result since 2^{2^n}=4^{2^{n-1}}.)

    @OP: You can prove it by induction, using the fact that 2^{2^n}-1 = (2^{2^{n-1}})^2 - 1 = (2^{2^{n-1}}-1)(2^{2^{n-1}} + 1)
    Are you saying 2^{2^n} \not= 4^n ?

    edit: if so why?
    Last edited by deejayy; 31-03-2012 at 15:05.
  9. nuodai's Avatar
    9 31-03-2012  15:04
    • PS Helper
    • TSR Legend
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by deejayy)
    Are you saying 2^{2^n} \not= 4^n ?
    Yes.

    (Original post by deejayy)
    edit: if so why?
    For instance 256 = 2^8 = 2^{2^3} \ne 4^3 = 64.
    Last edited by nuodai; 31-03-2012 at 15:07.
  10. deejayy's Avatar
    10 31-03-2012  15:10
    • Adored and Respected Member
    • Location: Melbourne
    • Posts: 505
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by nuodai)
    Yes.


    For instance 256 = 2^8 = 2^{2^3} \ne 4^3 = 64.
    Why though? I think I dont understand indices entirely.

    For instance 2^2^n \ne 2^{2^n} Why is this true?
  11. nuodai's Avatar
    11 31-03-2012  15:12
    • PS Helper
    • TSR Legend
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by deejayy)
    Why though? I think I dont understand indices entirely.

    For instance 2^2^n \ne 2^{2^n} Why is this true?
    I've just shown you why it's true. It's because (a^b)^c = a^{bc}, but it is not true that (a^b)^c = a^{b^c}; the latter means a^{(b^c)}.

    Edit: You'll need to fix your understanding of indices before you do STEP in June!

    Edit 2: To elaborate, you should try and lose the tendency to think "they look like they should be equal, so I need a reason why they're not" -- you should think "they look like they should be equal, so I'm going to prove that they are". Then when you try and fail to prove that they're equal, and instead find a counterexample, it's not such a shock. Think about what these things mean. (a^b)^c = a^{bc} means that you multiply a by itself bc times, whereas a^{b^c} means that you multiply a by itself b^c times. Clearly bc \ne b^c, so why should a^{bc} = a^{b^c}?
    Last edited by nuodai; 31-03-2012 at 15:17.
  12. TheMagicMan's Avatar
    12 31-03-2012  15:35
    • Overlord in Training
    • Posts: 2,940
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by nuodai)
    I've just shown you why it's true. It's because (a^b)^c = a^{bc}, but it is not true that (a^b)^c = a^{b^c}; the latter means a^{(b^c)}.

    Edit: You'll need to fix your understanding of indices before you do STEP in June!

    Edit 2: To elaborate, you should try and lose the tendency to think "they look like they should be equal, so I need a reason why they're not" -- you should think "they look like they should be equal, so I'm going to prove that they are". Then when you try and fail to prove that they're equal, and instead find a counterexample, it's not such a shock. Think about what these things mean. (a^b)^c = a^{bc} means that you multiply a by itself bc times, whereas a^{b^c} means that you multiply a by itself b^c times. Clearly bc \ne b^c, so why should a^{bc} = a^{b^c}?
    The method involving 4 does still work, namely because 2^{2^n}=4^{2^{n-1}} just not for the reason suggested!
  13. nuodai's Avatar
    13 31-03-2012  16:07
    • PS Helper
    • TSR Legend
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by TheMagicMan)
    The method involving 4 does still work, namely because 2^{2^n}=4^{2^{n-1}} just not for the reason suggested!
    Indeed (I said as much in my first reply!).
  14. Dog4444's Avatar
    14 01-04-2012  01:02
    • Exalted and Worshipped Member
    • Posts: 968
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by obbsidian)
    Can anyone see why 2^(2^n) is congruent to 1 mod 3?

    Thanks.
    2\equiv -1 (mod 3)
    Because 2^n is even
    2^{2^n}\equiv -1^{2^n}\equiv 1 (mod 3)

    Why you people make things way more complicated?
    Post rating:
    5
  15. nuodai's Avatar
    15 01-04-2012  11:24
    • PS Helper
    • TSR Legend
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by Dog4444)
    2\equiv -1 (mod 3)
    Because 2^n is even
    2^{2^n}\equiv -1^{2^n}\equiv 1 (mod 3)

    Why you people make things way more complicated?
    Well played, sir!
    Post rating:
    1
  16. ben-smith's Avatar
    16 01-04-2012  12:37
    • Overlord in Training
    • Location: Hilbert Space
    • Posts: 2,367
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by Dog4444)
    2\equiv -1 (mod 3)
    Because 2^n is even
    2^{2^n}\equiv -1^{2^n}\equiv 1 (mod 3)

    Why you people make things way more complicated?
    tbf, Mod arithmetic had been mentioned earlier but I guess people wanted a more elementary solution.
  17. Dog4444's Avatar
    17 01-04-2012  13:02
    • Exalted and Worshipped Member
    • Posts: 968
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by ben-smith)
    tbf, Mod arithmetic had been mentioned earlier but I guess people wanted a more elementary solution.
    It's much more elementary than induction.
  18. ben-smith's Avatar
    18 01-04-2012  13:11
    • Overlord in Training
    • Location: Hilbert Space
    • Posts: 2,367
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by Dog4444)
    It's much more elementary than induction.
    I can't say I agree though, personally, I would just binomially expand (3-1)^(2^n) and show that the only term without a 3 in is 1. This is essentially mod arithmetic but without the assumptions.
  19. gff's Avatar
    19 02-04-2012  23:42
    • Exalted and Worshipped Member
    • Location: Milky way Posts: μ(Ø)
    Re: 2^(2^n) is congruent to 1 mod 3?
    (Original post by Dog4444)
    It's much more elementary than induction.
    I would probably describe it as more elegant in comparison with the induction, as it isn't more elementary.
    (The result you used is indeed proved by induction.)


    For example, I could prove Fermat's Little theorem in the following manner.
    However, this does not make it near more elementary than the proof by induction and the binomial theorem given in the above link.
    Spoiler:
    Show

    The following is basically asserting standard results of Group Theory.


    If p \nmid a for a prime p, then a^{p - 1} \equiv 1\ (mod\ p).

    Proof:
    Since p is a prime, it follows that \mathbb{Z}_{p} is a field, and consequently that (\mathbb{Z}^{*}_{p}, \cdot) is a group.
    Therefore, because p \nmid a implies that a \in \mathbb{Z}^{*}_{p}, by Lagrange's theorem we conclude that a^{p - 1} \equiv 1\ (mod\ p).


    Anyway, +rep for spotting it.

    (Original post by ben-smith)
    I can't say I agree though, personally, I would just binomially expand (3-1)^(2^n) and show that the only term without a 3 in is 1. This is essentially mod arithmetic but without the assumptions.
    I agree with this, and for everybody planning to do STEP, I think binomial and induction must be our best friends.
Sign in to Reply
Search Thread
Advanced Search
Share this discussion:  
Useful resources

Articles:

Study Help rules and posting guidelinesStudy Help Member of the Month nominationsGuide to MathematicsMathematics resourcesMathematics websitesMathematics revision notes in the TSR wikiCambridge Assessment admissions tests (including STEP)How to use LaTeXCareers in Mathematics

Useful Dates:

Quick Link:

Unanswered Maths Threads

Groups associated with this forum:

View associated groups
Article updates
Moderators

We have a brilliant team of more than 60 volunteers looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is moderated by:

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22

Registered Office: International House, Queens Road, Brighton, BN1 3XE

Shortcuts

Get Started

TSR Group

Using TSR

Info

Connect with TSR

Reputation gems:
The Reputation gems seen here indicate how well reputed the user is, red gem indicate negative reputation and green indicates a good rep.
Post rating score:
These scores show if a post has been positively or negatively rated by our members.