# 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!!

-

You arrived at an expression of the form $$a^2-b^2=cn$$ and your next step was to compute $\gcd(c,n)$, which is not helpful in this context. Note that you can write the LHS as a product and rather try to find the $\gcd$ of one of these factors with $n$.
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}$.