Find all positive integer pairs $(a,b)$ such that, $$\frac{10^{a!} - 3^b +1}{2^a}$$is a perfect square.
Problem
Source: 2024 Turkey TST P4
Tags: number theory, modular arithmetic, Olympiad Number Theory, Perfect Squares, factorial
19.03.2024 01:09
Just an idea, might finish later. $(a,b) = (1,1), (1,2)$ are solutions. $a=2$ has no solutions, from now on assume $a \ge 3$. We have $2^a | 10^{a!}$, so $\nu_2(3^b-1) \ge a$ or $b = 2^{a-1} \cdot x$, for some positive integer $x$ (also establishes $b$ even). We also can establish $a$ odd via $\pmod 3$. we can even get $a \equiv 1 \pmod 6$ with mod $9$, but anyway I think the main idea is this: Write as \[10^{a!} +1 = 2^a n^2 + 3^b\] The left hand side will most of the time be $\equiv 2 \pmod{p}$ for a lot of primes and the right hand side you want $2$ and $3$ have a few solutions $\pmod p$, and $n^2$ has $\frac{p-1}{2}$ solutions at most, and then no solutions in this manner. Well I tried $p=7$ and $p=11$ but I couldn't find anything. Also $\nu_5$ doesn't seem useful, thats my progression edit: $p=11$ does work, nvm
19.03.2024 03:12
swynca wrote: Find all positive integer pairs $(a,b)$ such that, $$\frac{10^{a!} - 3^b +1}{2^a}$$is a perfect square. If $a>=3$ $10^{a!}-3^{2^{a-2}c}+1=2^an^2$ By $mod3$ we have $a=1(mod2)$ For $a=3$ no solution. For $a>3$ we have: By $mod5$ we get $5|RHS$ so $25|RHS$ ego gives $25|LH$ and so $5|c$ By $mod11$ we get $LHS=1-1+1=1(mod11)$ while $RHS=2^an^2=2x^2(mod11)$ So we $2x^2\equiv 1(mod11)\Leftrightarrow x^2\equiv 6(mod11)$ But $(\frac{6}{11})=(\frac{2}{11})(\frac{3}{11})=-(\frac{3}{11})=(\frac{11}{3})=(\frac{2}{3})=-1$ Which means that no such $x$ exist. For $a=1$ we get $b=1,2$ For $a=2$ no sollution.
19.03.2024 12:16
Here is my overkill solution from the contest:
19.03.2024 16:59
\[10^{a!}-3^b+1=k^2.2^{a}\]We have $2\equiv LHS\equiv RHS\equiv k^2.2^{a}(mod \ 3)\implies a$ is odd. $2^{a}|10^{a!}-3^b+1\implies 2^{a}|3^b-1\implies a\leq v_2(3^b-1)=2+v_2(b)\implies 2^{a-2}|b$. $i)a\geq 5$, we have $4|b$. $0\equiv LHS \equiv k^2.2^{a}(mod \ 5)$ since $3^b\equiv 1(mod \ 5)$ thus $5|k\implies 25|k^2|10^{a!}-3^b+1\implies 25|3^b-1$ If we denote $b=4c,$ then $2\leq v_5(3^{4c}-1)=v_5(81^c-1)=v_5(80)+v_5(c)=1+v_5(c)\implies 5|c\implies 5|b$. $3^x\equiv \{3,9,5,4,1\}(mod \ 11)$ $3^b\equiv 1(mod \ 11)$ since $5|b$ We get that $1\equiv 1-1+1\equiv LHS\equiv RHS\equiv 2.(k.2^{\frac{a-1}{2}})^2\equiv \{0,2,8,7,10,9\}(mod \ 11)$ which gives a contradiction. $ii)a=3$, $10^6-3^b+1=8k^2$ $2-3^b\equiv 8k^2\equiv 8.\{0,1,4,9,5,3\}\equiv \{0,8,10,6,7,2\}(mod \ 11)\implies 3^b\equiv 0,2,3,5,6,7(mod \ 11)\implies b\equiv 1,3(mod \ 5)$ Also $8|3^b-1\implies b$ is even. If $4|b$, then $5|b$ with the same reason in $i$ case but $20|b$ is not possible since $3^b<10^6$. So $b\equiv 2(mod \ 4)$ $\implies b\equiv 6,18(mod \ 20)$ If $b\equiv 18(mod \ 20),$ then $10^6>3^b\geq 3^{18}=9^9\implies 10^2>9^3$ which is obviously false. Thus $b\equiv 6(mod \ 20)\implies b=6$ $10^6-3^6+1=8k^2\iff k^2=124909\implies 353<k<354$ which is not possible. $iii)a=1$, $11-3^b=2k^2\implies \boxed{(1,1)}$ and $\boxed{(1,2)}$
22.03.2024 18:47
Firstly, note that $a$ is odd and $b$ is even. When $a>3$, $\pmod{16} \implies 4|b$. Then $\pmod{5}$ and $\pmod{25}$ yields $5|b$ which means $3^b=1 \pmod{11}$ and $2^a * k^2=1 \pmod{11}$ which hasn't got any solution... $a=1$ and $a=3$ are "ez" cases.
01.07.2024 16:47
Made mistake
01.07.2024 18:15
sami1618 wrote: Notice that $v_2\left(\frac{10^{a!}}{2^a}\right)=a!-a$. As $a!-a$ is odd we must have that $v_2\left(\frac{3^b-1}{2^a}\right)=a!-a$ Why? Maybe $v_2\left(\frac{3^b-1}{2^a} \right)<a! -a$ and even and thus $v_2\left (\frac{10^{a!} - 3^b +1}{2^a} \right)$ is also even?
05.07.2024 16:19
The pairs are $\boxed{(1,1),(1,2)}$ Firstly, mod $3$ we know that $a$ is odd. Suppose $a \neq 1,3$, so $a \geq 5$. Then $2(10^{a!}-3^b+1)$ is also a perfect square. Also, because the original number is integer, $3^b-1 \vdots 2^a$, from which by LTE Lemma we get that $v_2(b)+2 \geq a$, so $b \vdots 8 \vdots 4$. Then $3^b-1 \vdots 3^4-1 \vdots 5$. Because $10^{a!} \vdots 25$, $3^b-1 \vdots 25$, but then by LTE on 5 once again $b \vdots 5$, then $3^b-1 \vdots 3^5-1 \vdots 11$. Then mod 11 our perfect square is congruent to $2$, however it is not a quadratic residue. Contradiction Hence, $a=1$ or $a=3$ Case $a=1$: $\frac{11-3^b}{2}$ is a perfect square when $b=1,2$ Case $a=3$: $\frac{10^6-3^b+1}{8}$ is a perfect square. Just for it to be positive $b \leq 12$. If $b \vdots 4$ or $b \vdots 5$, same argument holds as above, but also by LTE $b$ is even, so the possible cases are $b=2,6$. If $b=2$, then $50^3-1$ should be a perfect square, but it is $3$ mod 4. If $b=6$, then $50^3-91$ should be a perfect square, which fails mod $8$