<s>[INST] Show $(3306 \cdot 3834)^2 - (11^2 \cdot 13 \cdot 17^2)^2 $ is divisible by $10875593$ Let $n = 10875593 $ 
Given $3306^2 - n = 11\cdot 17^3$ and $3834^2 - n = 11^3\cdot 13^2 \cdot 17$ 
Deduce that $(3306 \cdot 3834)^2 - (11^2 \cdot 13 \cdot 17^2)^2 $ is divisible by $n$. Then use a calculator and the Euclidean Algorithm to find a factor of $n$. What is the smallest $a$ such that $a^2 - n $ is a square?
Hi everyone, thanks in advance for the help. Here is what I have so far, first part seemed reasonably easy:
Given $3306^2 - n = 11\cdot 17^3$ and $3834^2 - n = 11^3\cdot 13^2 \cdot 17$
Then  $(3306^2 - n)(3834^2 - n) = (11\cdot 17^3)(11^3\cdot 13^2 \cdot 17) $
so, $(3306 \cdot 3834)^2 - (11^2 \cdot 13 \cdot 17^2)^2 = 3306^2n + 3834^2n $
therefore, LHS is divisble by n and = $ 3306^2 + 3834^2 $
The next part, I used the Euclidean Algorithm, and as I understand it so far, it takes two arguments, so I used $n$ and $ 3306^2 + 3834^2 $, I obtained the gcd to be 1.
Which seems to me that $n$ could be prime? I understand that the Euclidean Algorithm does not imply this, but should I just  pick random numbers to try with $n$ until I find otherwise? What sort of process should I use here?
For the final part of the question, I have tried to use Fermat's factorization method. By Fermat's factorization method, I know that $a >= \sqrt{n}$, so I have simply started from $ 3397^2 - n $ to try and find a perfect square. 
I've tried enough iterations to feel like this is not the way to go about it, but we're in week 1 of the semester and I am a bit stuck.
Any hints or directions would be greatly appreciated!!
 [/INST] Since $(3306 \cdot 3834)^2 - (11^2 \cdot 13 \cdot 17^2)^2= mn$, you need to calculate gcd of $(3306 \cdot 3834) - (11^2 \cdot 13 \cdot 17^2)$ and $n$ and gcd of $(3306 \cdot 3834) + (11^2 \cdot 13 \cdot 17^2)$ and $n$. One of these should give a factor of $n$. This is a standard technique of factoring $n$ where we try to express $n$ as $x^{2} - y^{2}$.
</s>