Find all pairs of positive integers $(n,t)$ such that $6^n+1=n^2t$, and $(n,29 \times 197)=1$
Problem
Source: 2016 Korea Winter Camp 2nd Test #6
Tags: number theory
25.01.2016 10:26
Very similar with this problem, and can be solved in the same way. Find all positive integer $n$ such that $n^2|2^n+1$
25.01.2016 12:00
$(n; t) = (1; 7)$ is a solution to this problem. Note that $n$ is odd and $\text{gcd}(n; 3) = 1$. Consider $n \ge 3$: Let $p$ be a smallest prime divisor of $n$. We have $6^{2n} \equiv 1 \pmod{p^{2}}$. On other hand, by Euler's theorem: $6^{p(p - 1)} \equiv 1\pmod{p^{2}}$. Hence, $\text{ord}_{p^{2}}(6)\mid \text{gcd}(p(p - 1); 2n) = 2p \implies 6^{2p} \equiv 1 \pmod{p^{2}}$. Notice that $\text{gcd}(6^{p} - 1; 6^{p} + 1) = 1$. So we have $p^{2} \mid 6^{p} - 1$ or $p^{2}\mid 6^{p} + 1$. Case 1: $6^{p} \equiv 1 \pmod{p}$. Apply Fermat's theorem, we get $p = 5$. Contradition. Case 2: $6^{p} \equiv -1 \pmod{p} \implies p = 7$ Setting $n = 7m$, we get $6^{7m} + 1 = 49m^{2}t \iff (6^{7})^{m} + 1 = 49m^{2}.t$ Notice that $6^{7} + 1 = 7^{2}.29.197$ If $7\mid m$, by LTE's lemma, $v_{7}(LHS) = 2 + v_{7}(m) < v_{7}(49) + v_{7}(m^{2}) \le v_{7}(RHS)$, contradition, and notice that $ \text{gcd}(m; 29.197) = 1$. Let $q$ be a smallest prime factor of $n$. As above, $\text{gcd}(q; 7.29.197) = 1$ We have, $(6^{7})^{2m} \equiv 1\pmod{q}$ and by Fermat little's theorem, $(6^{7})^{q - 1} \equiv 1\pmod{q}$, then $6^14 - 1 \vdots q$, so $q = 5$ or $q = 55987$. Try on the condition, which is contradition. So we have $m = 1$. Which means $n = 7$, and $t = 29.197$.
23.01.2017 23:20
IMO 1990, problem 3.