Question

prove that \[3^{2^{n}}-1\] can be written as the sum of two squares for all positive integers n.

Answer 1

\((3^{2^{n-1}})^2\) and \(i^2\) are both perfect squares, solved! :^)

Answer 2

lol yes correct :D

Answer 3

today ima post lots of ques like this (:

Answer 4

better ones xD

Answer 5

Ok but seriously this is as far as I've gotten:

\[(3^{2^{n-1}}+1)(3^{2^{n-1}}-1)=a^2+b^2\]

I feel like I've seen this sorta thing before, gotta think how to continue (if this is even a step in the right direction).

Answer 6

It is sufficient to show that none of the prime divisors of \(3^{2^n}-1\) are of form \(4k+3\)

Answer 7

but since this is supposed to be trick questions, im not gonna attempt... :)

Answer 8

Ok time for me to make a serious second attempt at internalizing Fermat's little theorem I guess.

Answer 9

Well maybe I'm just assuming that's going to be useful here, beats me.

Answer 10

the prime factorization has a really interesting pattern
http://www.wolframalpha.com/input/?i=Table%5Bfactor+3%5E2%5En-1%2C%7Bn%2C1%2C6%7D%5D

for the first 6 terms that i wolfram gave, each subsequent term is giving a new prime number

Answer 11

2^3,
2^4×5,
2^5×5×41,
2^6×5×17×41×193,
2^7×5×17×41×193×21523361,
2^8×5×17×41×193×21523361×926510094425921

Answer 12

except for 2, all the prime factors are of form 4k+1
so we can represent the terms as sum of two squares..

Answer 13

Why is this true?

\(\color{blue}{\text{Originally Posted by}}\) @ganeshie8
It is sufficient to show that none of the prime divisors of \(3^{2^n}-1\) are of form \(4k+3\)
\(\color{blue}{\text{End of Quote}}\)

Answer 14

that is due to fermat
https://www.math.hmc.edu/funfacts/ffiles/20008.5.shtml

Answer 15

if any prime factors are of form 4k+3, then they must come in even powers...
so we're good if we somehow show that none of the prime divisors are of form 4k+3

Answer 16

the pattern just keeps going with a new prime of form \(4k+1\) with each subsequent term :
\[a_n = 2p_na_{n-1}\]

Answer 17

conjecture :
every odd prime divisor of \(3^{2^n}-1\) is of form \(4k+1\)

Answer 18

Interesting, so there could still be prime factors of the form 4k+3 as long as they occur in pairs, makes sense but not sure how to show this. Gonna grab some more coffee and think about this.

Answer 19

Wait, how sure are you of this pattern, or is this just a guess?

\(\color{blue}{\text{Originally Posted by}}\) @ganeshie8
the pattern just keeps going with a new prime of form \(4k+1\) with each subsequent term :
\[a_n = 2p_na_{n-1}\]
\(\color{blue}{\text{End of Quote}}\)

Answer 20

yes thats correct :)

this can help understand - http://prntscr.com/928baa

Answer 21

yes that is just a guess @Kainui ... i don't have any proofs yet..

Answer 22

i have checked the first 11 terms and saw that pattern...
but i have a strong feeling that the pattern must break at some point

Answer 23

Hahaha ok ok, I am just in unfamiliar territory so I wasn't sure where the line is between stuff you know and stuff you're guessing at.

I am noticing though we have this sorta recursion pattern going,

\[(3^{2^{n+1}}-1) = (3^{2^{n}}-1)*a_n \]

I don't know if there's anything we can say about \(a_n=3^{2^n}+1\), but basically our number is a product of these \(a_n\) values.

Answer 24

yeah that also means \(a_i\mid a_j\) for all \(i\le j\)

Answer 25

Cute form:

\[3^{2^n}-1 = 2 \prod_{k=1}^n (3^{2^k}+1)\]

Answer 26

aww

Answer 27

Cute form:

\[3^{2^n}-1 = 2 \prod_{k=0}^{\color{red}{n-1}} (3^{2^k}+1)\]

Answer 28

Redemption alternate cute form:

\[3^{2^n}-1 = 2 \sum_{k=0}^{2^n-1} 3^k\]

Answer 29

that looks nice but sum may not be so useful when analysing prime factor though...

Answer 30

Redemption alternate cute form:

\[3^{2^n}-1 = 2 \sum_{k=0}^{2^{\color{red}{n-1}}} 3^k\]

(just nitpicking :) )

Answer 31

Wait that's not right though is it?

Answer 32

you're just expanding using \(x^n-y^n = (x-y)(stuff)\) right ?

Answer 33

No, this is the geometric series

Answer 34

they are same..

Answer 35

\[x^n-y^n = (x-y)(x^{n-1}+x^{n-2}y + \cdots + y^{n-1})\]

Answer 36

that identity follows from geometric series yeah :)

Answer 37

\[\frac{x^a - 1}{x-1} = \sum_{k=0}^{a-1} x^k\]
\(x=3\), \(a=2^n\)

Answer 38

it is a mystery why that sequence is laying one prime with each subsequent term

this cannot be true, it should break at some point...

Answer 39

\[3^{2^n}-1 = 2 \sum_{k=0}^{2^n-1} 3^k\]

If we think back to how all Mersenne primes were of the form of \(2^p-1\) because if p isn't prime, for numbers like p=6 we would have in binary all the factors of 6 have representations:


1*111111=11*10101=111*1001


Similarly I think we can look at this representation in base 3 and see that all its prime factors come in pairs because factors come in pairs.

Answer 40

So what that means is that at least saves it because them coming in pairs means \(3^2 \equiv 1 \mod 4\) is maintained... Which doesn't really prove the conjecture either way haha.

Answer 41

So maybe it turns out for higher numbers there are some 4n+3 primes and it doesn't just multiply in a single new prime every time... I don't know.

Answer 42

is it easy to prove that \(p\mid a_n \implies p\mid a_{n+1}\) ?

does that follow from your earlier representation of \(3^{2^n}-1\) as a product ?

Answer 43

Actually there's a funny thing going on here when there are a prime number of powers of 3 in that sum, that means \(2^n-1\) is prime... which means n is prime... lol

I'm not really sure I'm not actually going anywhere anymore I'm just sorta exploring around.

Answer 44

Nvm, it trivially follows from earlier statement

\(a_{n+1} = 3^{2^{n+1}}-1 = (3^{2^n}+1)*a_{n}\)

if \(p\mid a_{n}\), we do get \(p\mid a_{n+1}\)

Answer 45

Yes what you have just written is true, but I think the way I did it was the + terms were the \(a_n\), so just saying that to make sure you're not mixing anything up, I think this got sorta confusing. Well at least I'm confused lol

Answer 46

since our goal is to prove that every prime factor, \(p\), is of form \(4k+1\), I guess below might work :

If we "somehow" show that \(4\) is the order of \(3^{2^{n-2}}\) in modulus \(p\), then we can argue that the order must divide \(\phi(p)\).

\(4\mid \phi(p) \)

\(4\mid p-1\)

\(p=4k+1\)

Answer 47

Got it !

new prime(s) of \(a_n\), that are not occured in the previous terms will be of form \(2^na+1\)

(il post a proof for above statement shortly )

clearly \( 2^na+1\equiv 1\pmod{4}\)
so we're done !

Answer 48

Ohhhh nice!

Answer 49

(proof) every new prime divisor of \(a_n\) is of form \(2^na+1\)

\(a_{n} = 3^{2^n}-1 = (3^{2^{n-1}}+1) (3^{2^{n-1}}-1)= (3^{2^{n-1}}+1)*a_{n-1}\)

New prime(s) occur in the expression \(3^{2^{n-1}}+1\). So just consider this.

Let \(p\) be any "odd" prime divisor of \(3^{2^{n-1}}+1\).
\(3^{2^{n-1}}+1\equiv 0 \pmod{p}\)
\(3^{2^{n-1}}\equiv -1 \pmod{p}\)
\(3^{2^n}\equiv 1 \pmod{p}\)

that means \(2^n\)is the order of \(3\) in modulus \(p\). it follows
\(2^n \mid \phi(p)\)
\(2^n\mid p-1\)
\(p=2^na+1\) for some integer \(a\)

Answer 50

Overall we have proved that the odd prime divisors of \(3^{2^n}-1\) are of form \(4k+1\)

Answer 51

Awesome, this is giving me some more ideas. Also, I am trying to see a little more about these prime divisors and what they are, it looks like we have:

\[10 \equiv 0 \mod p\]
Is this at all surprising to us?

Answer 52

Awesome, this is giving me some more ideas. Also, I am trying to see a little more about these prime divisors and what they are, it looks like we have:

\[10 \equiv 0 \mod p\]
Is this at all surprising to us?

Answer 53

\(10\equiv 0\) ?

Answer 54

Let \(p\) be any "odd" prime divisor of \(3^{2^{n-1}}+1\).
\(3^{2^{n-1}}\equiv -1 \pmod{p}\)
\(3^{2^n}\equiv 1 \pmod{p}\)

Sorry I forgot to put this, I'm pretty tired:
\(1\equiv 3^{2^n} \equiv 9*3^{2^{n-1}}\equiv 9*(-1) \pmod{p}\)

Answer 55

that is true only in one direction, they are not independent congruences...

Answer 56

\(3^{2^{n-1}}\equiv -1 \pmod{p} \implies 3^{2^n}\equiv 1 \pmod{p}\)

not the other way...

Answer 57

Lol ok not sure what that means I'll sleep on it I guess

Answer 58

we can say \(a \equiv b \pmod{n} \implies a^2\equiv b^2\pmod {7}\)

but the converse isn't true

we cannot take the statement \(a^2\equiv b^2\pmod{n}\) and plugin \(a=b\)

Answer 59

\(n\mid (a^2-b^2)\)

\(n\mid (a+b)(a-b)\)

\(n\) need not be a divisor of \(a-b\)

Answer 60

Also \(3^{2^n}\) and \(9*3^{2^{n-1}}\) are not same things

Answer 61

shuld i give some hint?

Answer 62

\[Solution-->\]
i just factored it\[3^{2^n}-1=(3^{2^{n-1}}+1^2).......(3^8+1^2)(3^4+1^2)(3^2+1^2)(3^2-1^2)\]\[3^{2^n}-1=(3^{2^{n-1}}+1^2).......(3^8+1^2)(3^4+1^2)(3^2+1^2)(2^2+2^2)\]
note that the product of sum of 2squares can be written as a sum of 2squares-\[(a^2+b^2)(c^2+d^2)=(ad-bc)^2 +(ac+bd)^2\]hence proved