You are Here: Home

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

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

Announcements Posted on
Find out how cards are replacing warnings on TSR...read more 03-12-2013
1. 2^(2^n) is congruent to 1 mod 3?
Can anyone see why 2^(2^n) is congruent to 1 mod 3?

Thanks.
2. 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 16:03.
3. 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. Re: 2^(2^n) is congruent to 1 mod 3?
(Original post by TenOfThem)
because

All the bits apart from the 1 have 3 to some power so are 0 [mod3]
You cold just invoke that if then (not that it makes any difference)
5. Re: 2^(2^n) is congruent to 1 mod 3?
(Original post by TenOfThem)
because

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. Re: 2^(2^n) is congruent to 1 mod 3?
(Original post by TenOfThem)
because

All the bits apart from the 1 have 3 to some power so are 0 [mod3]
That's and not . (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 .)

@OP: You can prove it by induction, using the fact that
Last edited by nuodai; 31-03-2012 at 16:00.
7. 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. Re: 2^(2^n) is congruent to 1 mod 3?
(Original post by nuodai)
That's and not . (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 .)

@OP: You can prove it by induction, using the fact that
Are you saying ?

edit: if so why?
Last edited by deejayy; 31-03-2012 at 16:05.
9. Re: 2^(2^n) is congruent to 1 mod 3?
(Original post by deejayy)
Are you saying ?
Yes.

(Original post by deejayy)
edit: if so why?
For instance .
Last edited by nuodai; 31-03-2012 at 16:07.
10. Re: 2^(2^n) is congruent to 1 mod 3?
(Original post by nuodai)
Yes.

For instance .
Why though? I think I dont understand indices entirely.

For instance Why is this true?
11. 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 Why is this true?
I've just shown you why it's true. It's because , but it is not true that ; the latter means .

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. means that you multiply by itself times, whereas means that you multiply by itself times. Clearly , so why should ?
Last edited by nuodai; 31-03-2012 at 16:17.
12. 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 , but it is not true that ; the latter means .

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. means that you multiply by itself times, whereas means that you multiply by itself times. Clearly , so why should ?
The method involving 4 does still work, namely because just not for the reason suggested!
13. Re: 2^(2^n) is congruent to 1 mod 3?
(Original post by TheMagicMan)
The method involving 4 does still work, namely because just not for the reason suggested!
Indeed (I said as much in my first reply!).
14. 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.

Because 2^n is even

Why you people make things way more complicated?
15. Re: 2^(2^n) is congruent to 1 mod 3?
(Original post by Dog4444)

Because 2^n is even

Why you people make things way more complicated?
Well played, sir!
16. Re: 2^(2^n) is congruent to 1 mod 3?
(Original post by Dog4444)

Because 2^n is even

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. 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. 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. 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 for a prime , then .

Proof:
Since is a prime, it follows that is a field, and consequently that is a group.
Therefore, because implies that , by Lagrange's theorem we conclude that .

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.

## Step 2: Register

Thanks for posting! You just need to create an account in order to submit the post
1. this can't be left blank

this is what you'll be called on TSR

2. this can't be left blank

never shared and never spammed

3. this can't be left blank

6 characters or longer with both numbers and letters is safer

4. this can't be left empty
1. By completing the slider below you agree to The Student Room's terms & conditions and site rules

2. Slide the button to the right to create your account

You don't slide that way? No problem.

Last updated: April 3, 2012
Study resources