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.
 A: $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.
A: $3n+1=x^2$
$4n+1=y^2$
$4y^2-3x^2=1$
Put $z=2y $
$z^2-3x^2=1$
One of solution is: $(z_0,x_0)=(2,1) $
Other solutions are given by:
$(z_n+ \sqrt3 y_n)=(2+ \sqrt 3)^{n} $
From above we get ,
$z_{n+1}=7z_n+12y_n $
And
$y_{n+1}=4z_n+7y_n $
Or (in terms of $x_n $);
$x_{n+1}=7x_n+6y_n $
$y_{n+1}=8x_n+7y_n $
Now,
$x_{n+1} \equiv -y_n $ mod 7
$y_{n+1} \equiv x_n $   mod 7
${y_{n+1}}^2-{x_{n+1}}^2 \equiv n $
$\equiv {x_n}^2 -{y_n}^2 \equiv  -n $
$\equiv 0 $
A: 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.
A: 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$.
