room topic changed to Elementary number theory: [elementary-number-theory] [number-theory]

That's funny. I just wanted to introduce that I have no elementary-number-theory-proof for my congruency claim. Anyway, there are two statements, namely $x\equiv 1 \mod 2$ and: If $p$ is a prime dividing 3^n+5^n, then $p\equiv 1,2,4,8 \mod 15$.

This is actually stronger then the before mentioned congruences.

@benh you mean you have a proof, but it is not elementary?

depends on what you call elementary, it uses ramification of primes in number fields

In general, I think it is helpful to rewrite the equation we are starting with: assume $n^2-1 \mid 3^n+5^n$. We already know $3\mid n$, so let $n=3m$. Then $(3^{-1}) \equiv (3m^2) \mod n=9n^2-1§. (by the way, is there any way we can have LaTeX here?).

@benh that's interesting, you can add your proof here so we can see it later.

Yes, see here

By the way, $13\equiv13\pmod{15}$ yet $13\mid 3^{66}+5^{66}$.

Referring to TeX: Oh, you wrote that earlier, I am sorry! Thank you very much, this is brilliant.

Referring to math: right, I wasn't precise, I meant: if $p$ is a prime dividing $3^n+5^n$ with $n^2-1 \mid 3^n+5^n$, then $p\equiv 1,2,4,8$ mod 15. Otherwise $3$ would be another counter example

We have $n=3m$ and $3^{-1} = 3m^2 \mod 9m^2-1 =n^2-1$.

So $3^n+5^n \equiv 0 \Rightarrow (15m^2)^n \equiv -1 \mod n^2-1$

Let me call that (*), I think it is quite accessible for algebraic methods:

Suppose $n$ even.

I couldn't follow the second part, could you please elaborate it a bit?

Yes, $3^n+5^n \equiv 0 \Rightarrow 1+(3^{-1}5)^n \equiv 0$

...because $3$ and $n^2-1$ are coprime. Ok

right

So we supposed $n$ even. Then $-1$ is a quadratic residue mod $n^2-1$.

So $-1$ is a quadratic residue for all prime factors of $n^2-1$.

Thus, they are all of the form $p\equiv 1 \mod 4$

But does it matter the parity of $n$ for it to hold?

yes, because otherwise $-1$ would not necessarily be a quadratic residue.

we make use of (*) here

Oh, ok, I thought it was $n^2+1$.

Wait, it was $n^2-1$ in the problem, right?!

It is, it was my brain who didn't think so for a while. Heh

Sorry, for a moment i thought... anyway... so all prime factors are $p\equiv 1 \mod 4$.

Hence, $n^2-1$ is also $\equiv 1 \mod 4$

but $n$ even, so $n^2-1 \equiv 3 \mod 4$, a contradiction

Thus, n is odd.

everything ok until here?

This is an important result, if right. I think it is

Unfortunately, I'll leave for Christmas now. Please write the proofs, I'll read them when I come back. Merry Christmas :-)

Oh, * Merry Christmas! *

:)

I think I should go to sleep now, too, because in Europe it's very late... I just give a short sketch for today and complete the proof tomorrow if you like...

The main idea is to change from the ring of integers in $\Bbb Q$ to the ring of integers of $\Bbb Q(\sqrt{-15})$.

a prime is unramified in $\Bbb Q(\sqrt{-15})$ iff $p\equiv 7,11,13,14 \mod 15$.

() yields: Let $a = (-15)^{(m-1)/2}$, then $n^2-1\mid (15m^2)^n+1 = (1-a\sqrt{-15})(1+a\sqrt{-15})$, lets call this (*).

We know precisely how $\mathfrak{O}_{\Bbb Q(\sqrt{-15})}$ looks like and we can conclude that for an unramified prime (these are of the aforementioned form) $p\mid (n^2-1) $ implies $p\mid 1$ because it divides one of the two factors in (**), hence both coefficients of that factor. So any divisor of $n^2-1$ is necessarily unramified.

This leads to the claim, that all prime divisors of $n^2-1$ are of the form $p\equiv 1,2,4,8\mod 15$. This implies $5\equiv 3 \mod 3$.

One implication of this is that we have $n \equiv 3,93 \mod 120$ which should speed up your empirical research a bit.

I hope that it may also help finding other methods to tackle the problem.

Oh, might I say that this is my first real interaction with MSE-users, so... nice to meet you guys, you're great! :)

@benh Unramified means that it remains prime over the field extension, right?

I know nothing about algebraic number theory, I'll study it until I understand the proof.

Yes. We have a unique factorization in prime ideals in the ring of integers of $\Bbb Q(\sqrt{-15})$ and we know that the ring of integers is generated over $\Bbb Z$ by $\frac{1+\sqrt{-15}}{2}$. So we can reduce divisibility conditions for ramified primes to divisibility conditions in $\Bbb Z$.

The ramified primes in $\sqrt{-15}$ can be computed using a criterion that says that a prime $p$ is ramified iff the discriminant $d_K$ is a quadratic residue mod $p$.

In our case $d_K$ = -15

I was referring to divisibility conditions for unramified primes in the above post about factorization, not ramified primes, sorry.

You should post this in the question as a useful insight. Wider criticism is expected, since I know nothing about it, heh. I'm reading it and I'll ask some questions soon.