1
$\begingroup$

If a prime $p$ can be written as the sum of two squares, then one can construct this representation via Fermat descent if we know an $x$ such that $x^2 \equiv -1 \mod p$. Is there a possibility to say how much steps the Fermat descent will have without just going through the descent?

$\endgroup$
  • $\begingroup$ Are you asking whether is it possible to construct the representation by Fermat's descend or are you telling us? Because I don't see it that obvious. $\endgroup$ – Timbuc Jan 23 '15 at 19:05
  • $\begingroup$ It indeed is possible to construct the representation, starting from the value of $x$, by the Fermat descent method using the explicit step described by Euler. I take the question, then, to mean is there any way to tell from properties of $p$ how many descent steps will be needed. For example, for $p = 109, x = 33$ one step is needed: $109 \equiv 10 \mod 33; 33 \equiv 3 \mod 10; 3^2 + 1^2 \equiv 0 \mod 10$ so you are thru and the numbers are $10^2 + 3^2$. The answer to how many steps will be clearer if you express $p$ in the form of a continuant. $\endgroup$ – Mark Fischler Jan 23 '15 at 19:50
  • $\begingroup$ @Mark: I do not understand what you mean with "The answer to how many steps will be clearer if you express p in the form of a continuant." $\endgroup$ – Martin Jan 24 '15 at 11:10
  • $\begingroup$ What I meant is that this algorithm is very similar to the Euclid algorithm for finding a gcd.And in that algorithm, if it finds the gcd in $k$ steps after computing a sequnce of quotients $\{q_i\}$, then the starting largest number was $K(q_1, q_2,\ldots q_k)$ where $K$ is the $k$-th degree continuant polynomial, defined by $K_0() = 1, K_n(x_1\ldots x_n) = K_{n-1}(x_1\ldots x_{n-1})x_n+K_{n-2}(x_2\ldots x_{n-2})$. With this you can show that the gcd is found in at most $1+\log_\rho a$ steps, where $\rho$ is the golden ratio. I speculated that the same sort of thing happens for Fermat Descent $\endgroup$ – Mark Fischler Jan 28 '15 at 15:47
  • $\begingroup$ This is not te best formalism for this task. the best is to $b^2 \equiv -4 \pmod {4p}$ so that $b^2 = -4 + 4 pt$ in integers. Then $\langle p, b,t \rangle$ is a positive quadratic form $px^2 + b xy + t y^2$ that reduces to $\langle 1,0,1 \rangle$ in very few steps, the same business with the golden ratio mentioned by @MarkFischler. The reduction is by a matrix in $SL_2 \mathbb Z,$ its inverse shows how to write $p=x^2 + y^2$ in integers. $\endgroup$ – Will Jagy Jan 31 '15 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.