# If 4n+1 and 3n+1 are both perfect sqares, then 56|n. How can I prove this?

Prove that if $n$ is a natural number and $(3n+1)$ & $(4n+1)$ are both perfect squares, then $56$ will divide $n$.

Clearly we have to show that $7$ and $8$ both will divide $n$.

I considered first $3n+1=a^2$ and $4n+1=b^2$. $4n+1$ is a odd perfect square. - so we have $4n+1\equiv 1\pmod{8}$; from this $2|n$ so $3n+1$ is a odd perfect square. - so $3n+1\equiv 1\pmod{8}$ so $8|n$ but I can't show $7|n$. How do I show this?

Thanks for the help.

$3n+1=a^2$ and $4n+1=b^2$ gives $4a^2-3b^2=1$. With $x=2a$ and $y=b$ we get an instance of Pell's equation.

$$x^2-3y^2=1.$$

Trying small integers, it is obvious that the minimal solution is $4-3=1$, that is $x_1=2$ and $y_1=1$.

Therefore, all the solutions are of the form $(x_k,y_k)$ with $x_k+y_k\sqrt 3=(x_1+y_1\sqrt 3)^k$ or equivalently \begin{align} x_{k+1}&=2x_k+3y_k\\ y_{k+1}&=x_k+2y_k, \end{align} (which already works starting from the trivial solution $x_0=1$, $y_0=0$).

This gives $3y_{k+1} =3x_k+6y_k$ which implies \begin{align}&x_{k+2}-2x_{k+1}=3x_k+2x_{k+1}-4x_k\\ \Leftrightarrow &x_{k+2}-4x_{k+1}+x_k=0 \end{align} and $x_0=1$, $x_1=2$.

Clearly, the $x_i$ alternate in sign and we are only interested in the even ones which are those with odd index. \begin{align}x_{2k+1} &= 4x_{2k}-x_{2k-1}\\&=4(4x_{2k-1}-x_{2k-2})-x_{2k-1}\\ &=15x_{2k-1}-x_{2k-1}-x_{2k-3}\\&=14x_{2k-1}-x_{2k-3}.\end{align}

Upon division by two, we obtain the recurrence for the solutions $a_k$ to $3n+1=a^2$ subject to the other condition.

$$a_k=14a_{k-1}-a_{k-2},$$ with $a_0=1$ and $a_1=13(=\dfrac{x_3}2)$.

Now, it is trivial to check that modulo $3$, all $a_k$ are $\equiv 1$ because $14\cdot 1 - 1 \equiv 1 \mod 3$. Which implies that $3 \mid a^2-1$.

Furthermore, modulo $7$, all $a_k$ are $\equiv \pm 1$ because $a_k \equiv - a_{k-2} \mod 7$ which implies that $7 \mid a^2-1$.

And finally, modulo $4$, all $a_k$ are $\equiv 1$ because $14-1 \equiv 1 \mod 4$ which implies that $8 \mid (a-1)(a+1)=a^2-1$.

So, in summary, $56 \mid \dfrac{a^2-1}3$ as desired.

$$3n+1 = a^2$$ and $$4n+1 = b^2$$. As $$b^2 \equiv 1 \mod 4 \implies b \equiv \pm 1 \mod 4$$. So, $$4n +1 = (4k_1 \pm 1)^2 \implies n = 2k_1 (2k_1 \pm 1)$$. So, $$2 \mid n$$ , let $$n = 2n'$$. $$3n +1 = 2(3n')+1$$ hence $$a$$ is odd, say $$a = 2a'+1$$. $$6n' +1 = 4a'^2 + 4a' +1$$ $$\implies 3n' = 2a'(a'+1)$$. $$2 \mid a'(a'+1) \implies 4 \mid n'$$ (as $$4 \nmid 3$$). So $$\boxed{8 \mid n}$$

$$x^2 \equiv 0, 1,2,-3 \mod 7$$. If $$3n+1 \equiv 0 \implies n \equiv 2 \implies 4n+1 \equiv 2$$ (All in mod 7). If $$3n+1 \equiv 1 \implies n \equiv 0 \implies 4n+1 \equiv 1$$. If $$3n+1 \equiv 2 \implies n \equiv -2 \implies 4n+1 \equiv 0$$. If $$3n+1 \equiv -3 \implies n \equiv 1 \implies 4n+1 \equiv -2$$ (not possible). So, $$n \equiv 0,2,-2 \mod 7$$.

Now, we will show that $$n \equiv 2 \mod 7$$ is not possible. As $$n \equiv 0 \mod 8 \implies n \equiv 16 \mod 56$$. Let $$n = 56n'' +16$$. $$a^2 = 3(56n'' +16)+1 = 168n'' +49$$. So $$7 \mid a^2 \implies 7 \mid a \implies 49 \mid a^2$$. But $$49 \nmid 168$$ hence a contradiction. Similarly we can show that $$n \equiv -2 \mod 7$$ is ruled out. So $$\boxed{7 \mid n}$$

Hence $$\boxed{56 \mid n}$$ as $$gcd(8,7) = 1$$. $$\Box$$

$$3n+1=x^2$$ $$4n+1=y^2$$ $$4x^2-3y^2=1$$ Put $$z=2x\ \ \$$ $$z^2-3y^2=1$$

One of solution is: $$(z_0,y_0)=(2,1)$$

Other solutions are given by: $$(z_k+ \sqrt3 y_k)=(2+ \sqrt 3)^{k}$$

From above we get, $$z_{k+1}=7z_k+12y_k$$ And $$y_{k+1}=4z_k+7y_nk$$ (we use $$(2+\sqrt3)^2$$ to maintain parity of $$z$$)

Or (in terms of $$x_k$$);

$$x_{k+1}=7x_k+6y_k\ \ \ \$$ $$y_{n+1}=8x_k+7y_k$$

Now,

$$x_{k+1} \equiv -y_k \pmod 7$$

$$y_{k+1} \equiv x_k \pmod 7$$

Since $$y_0^2 - x_0^2 \equiv 0 \pmod 7$$, the claim follows by induction.

Let $3n+1=K^2$ and $4n+1=P^2$, where $P$ and $K$ are integers. Therefore, we know that $4(K^2)-3(P^2)=1$. Rearranging terms gives us $K^2= \frac {1+3P^2}4$. By testing values and guesswork we know that $P=13$ and $K=15$. Therefore $3n+1=169$, and then solving for $n$ gives us $n=56$.

For $$7 | n$$, consider adding $$4n+1$$ and $$3n+1$$.

Observe that we get $$7n + 2 = x^2 + y^2$$, where we can let $$4n+1 = x^2$$, and $$3n+1 = y^2$$. Now, we see that mod $$7$$, the only quadratic residues are $$0$$, $$1$$, $$2$$, $$4$$. The only way to get two squares summing to 2 mod 7 is either if both are congruent to $$1$$ mod $$7$$, or if one is $$0$$ mod $$7$$ and one is $$2$$ mod $$7$$.

If both are congruent to $$1$$ mod $$7$$, we have n is $$0$$ mod $$7$$, so we need to show that the other case is not possible.

We now try to multiply $$4n+1$$ by $$3n+1$$, to get $$12n^2 + 7n + 1$$. This mod 7 is $$5n^2 + 1$$. If one of the squares if $$0$$ mod 7, it means that the product is also 0 mod 7, meaning that $$5n^2 + 1 \equiv 0$$ mod $$7$$. This means that $$5n^2 \equiv 6$$ mod $$7$$, and hence that $$n^2 \equiv 5$$ mod $$7$$, which is an impossibility due to quadratic residues mod 7.