Are there natural number(s) $n$, such that $3^n+1$ has a divisor in the form $24k+20$
Problem
Source: Bulgarian Autumn Tournament 2022 10.3
Tags: number theory, Divisors
Assassino9931
21.11.2022 12:20
Clearly $n$ is odd by mod $4$, so $(-3)$ must be a quadratic residue mod a prime $\equiv 5 \pmod 6$, contradiction.
GM_YoanaMl
14.11.2023 00:27
Claim: There does not exist a natural number $n$ with this property. Proof: Suppose that there exist natural numbers $n$ and $k$, such that $24k+20|3^n+1$. This means that $3^n\equiv{-1}$ (mod $4$). If $n=2m$ we have $3^n\equiv{9^m}\equiv{1}$ (mod $4$) If $n=2m+1$ we have $3^n\equiv3.{9^m}\equiv{3}$ (mod $4$) $\implies{n}$ is odd. Claim: Every number of the form $6k+5$ has a prime divisor of the form $6l+5$. Proof.
(BWOC) Let's suppose that this is not true. Therefore all the prime factors of $6k+5$ are of the form $6l+1$, because $6k+5$ is not divisible by $2$ or $3$. But the product of these prime factors is also of the form $6l+1$, contradiction!
Using this we can assume WLOG that $6k+5=p$, where $p$ is a prime number. Now we have $3.(3^m)^2\equiv{-1}$ (mod $p$). Set $3^m=x$. We have $3x^2\equiv{-1}$ (mod $p$) We have $\left( \frac{3x^2}{p} \right)$ $=$ $\left( \frac{-1}{p} \right)$ $\iff$ $\left( \frac{3}{p} \right)$ $=$ $\left( \frac{-1}{p} \right)$. We will use the well-known
$\left( \frac{-1}{p} \right)$ $=1$ for odd prime $p$ $\iff p\equiv{1}$ (mod $4$).
We will use the following result: Law of Quadratic Reciprocity:
$\left( \frac{p}{q} \right)$ $\left( \frac{q}{p} \right)$ $=-1\iff $ $p\equiv{q}\equiv3$ (mod $4$) and $\left( \frac{p}{q} \right)$ $\left( \frac{q}{p} \right)$ $=1\iff p\equiv{1}$ (mod $4$) or $q\equiv{1}$ (mod $4$)
to prove the following Claim: $\left( \frac{3}{p} \right)$ $=1\iff p\equiv 1$ or $-1$ (mod $12$) Proof:
If $p\equiv{1}$ (mod $4$) $\iff p=4t+1$. By Law of Quadratic Reciprocity we have $\left( \frac{3}{p} \right)$ $=$ $\left( \frac{p}{3} \right)$.
If $p\equiv{1}$ (mod $3$) we have $\left( \frac{p}{3} \right)$ $=1$ and $4t+1\equiv{1}$ (mod $3$) $\iff$ $t\equiv{0}$ (mod $3$) $\implies p\equiv{1}$ (mod $12$)
If $p\equiv{2}$ (mod $3$) we have $\left( \frac{p}{3} \right)$ $=-1$ and $4t+1\equiv{2}$ (mod $3$) $\iff$ $t\equiv{1}$ (mod $3$) $\implies p\equiv{5}$ (mod $12$)
If $p\equiv{3}$ (mod $4$) $\iff p=4t+3$. By Law of Quadratic Reciprocity we have $\left( \frac{3}{p} \right)$ $=-$ $\left( \frac{p}{3} \right)$.
If $p\equiv{1}$ (mod $3$) we have $\left( \frac{p}{3} \right)$ $=1$ and $4t+3\equiv{1}$ (mod $3$) $\iff$ $t\equiv{1}$ (mod $3$) $\implies p\equiv{7}$ (mod $12$)
If $p\equiv{2}$ (mod $3$) we have $\left( \frac{p}{3} \right)$ $=-1$ and $4t+3\equiv{2}$ (mod $3$) $\iff$ $t\equiv{2}$ (mod $3$) $\implies p\equiv{11}$ (mod $12$)
Therefore $\left( \frac{3}{p} \right)$ $=1\iff p\equiv 1$ or $11$ (mod $12$) and $\left( \frac{3}{p} \right)$ $=-1\iff p\equiv 5$ or $7$ (mod $12$) and we are done.
We have $2$ cases: Case $1$: $p\equiv{1}$ (mod $4$) We have $6k+5\equiv{1}$ (mod $4$) $\iff$ $k\equiv{0}$ (mod $2$). Let $k=2s$ for some natural number $s$ We have $p=12s+5$. We also must have $\left( \frac{3}{p} \right)$ $ = 1$ by Law of Quadratic Reciprocity, but this contradicts our claim. Case $2$: $p\equiv{3}$ (mod $4$) We have $6k+5\equiv{3}$ (mod $4$) $\iff$ $k\equiv{1}$ (mod $2$). Let $k=2s+1$ for some natural number $s$ We have $p=12s+11$. We also must have $\left( \frac{3}{p} \right)$ $ = -1$ by Law of Quadratic Reciprocity, but this also contradicts our claim. Hence we have contradiction in all cases which finishes the solution.