Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

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$.

share|improve this answer

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}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.