Revision history [back]

If we start with an integer $n>0$ with known (or computable) factorization $n=\prod_{p\in P} p^{r(p)}$, for some finite set of primes $P$, each prime being one modulo $4$, and corresponding powers function $p\to r(p)$, then the algorithm to go straightforward to the result is as follows. Write each $p$ as a product $(a+ib)(a-ib)$ of two primes in $\Bbb R=\Bbb Z[i]$, $0 < a\le b$. If $p=2$ the representation is $(1+i)(1-i)$, and the factors are associated. Else the two factors are different primes. Now from each $p^{r(p)}$ prime power factorization in $\Bbb Z$ we take the corresponding factorization in $\Bbb Z$, $(a+ib)^r(p)(a-ib)^r(p)$, and distribute it in all ($r(p)$, $p\ne2$) possibilities in two conjugated factors $e(p),f(p)$ of same norm, $p^{r(p)}=e(p)f(p)$, $e(p)=A+iB$, $f(p)=\overline{e(p)}=A-iB$.

We obtain numerous factorizations $$\prod e(p)\cdot \prod f(p)\ ,$$ and writing $\prod e(p)=S+iT$, $\prod f(p)=S-iT$ the two numbers are relatively prime iff each choice $p^{r(p)}=e(p)f(p)$ has relatively prime factors $e(p),f(p)$. So we have in essence only two choices for $e(p)$, either $(a+ib)^r(p)$, or (a-ib)^r(p)$.

The algorithm is thus to start with an $n$, collect all prime powers, represent them as product of powers over $\Bbb Z[i]$, build for each $p$ the factor $e(p)$ in two ways for $p\ne 2$, compute $\prod e(p)=S+iT$, then $S^2+T^2=n$. Among the many generated solutions only the half is needed in case there is a prime $p\ne 2$ in $P$, because the choices $\prod e(p)=S+iT$, and $\prod e'(p)=S-iT$, with $e'=\bar e$ lead to the same solution. So for the first prime $p\ne 2$ we make one choice.

def reps(n):
    """Searching for all different representations n = S² + T², where n > 0 is an integer
    """
    sols = []    # and we append solutions sol one by one when found
    first_prime, choices, R = True, [], GaussianIntegers()

    for p, mul in factor(n):
        if p == 2:
            choices.append( [(1 + i)^mul] )
        elif p % 4 != 1:
            return []            
        else:
            pp = R(p).factor()[0][0]    # first factor of p seen in ZZ[i]
            if first_prime:
                first_prime = False
                choices.append( [pp^mul] )
            else:
                choices.append( [pp^mul, pp.conjugate()^mul] )
    for choice in cartesian_product(choices):
        S, T = R(prod(choice))
        S, T = abs(S), abs(T)
        if S > T:    S, T = T, S
        sols.append((S, T))
    sols.sort()
    return sols

Then with the above code:

sage: N = 10^40 + 1
sage: reps(N)
[(1, 100000000000000000000),
 (19999999800000001, 99999998000000020000),
 (21175073018521651199, 97732370700092384320),
 (21194619068964748801, 97728133730883635680),
 (27288575518388109025, 96204644618527795624),
 (47041175529588244705, 88244704117552958824),
 (47058823529411764705, 88235294117647058824),
 (64675591816386108385, 76269704491365444424)]
sage: factor(N)
17 * 5070721 * 5882353 * 19721061166646717498359681

An other check:

sage: N = 2^90 + 1
sage: factor(N)
5^2 * 13 * 37 * 41 * 61 * 109 * 181 * 1321 * 54001 * 29247661
sage: factor(len(reps(N)))
2^9

And we have all $2^9$ expected representation, the corresponding list of solutions is of course not shown. One more check:

sage: reps(5^20 * 13^20 * 17^20)
[(1120228314932443982452255202016, 2472109092323644501221860856287),
 (1222652640782476248129183940513, 2423087980638188359909730969616),
 (1808156181728664217638411829584, 2024056833293480968965675605087),
 (1891237057569836360342883758113, 1946652828318445656133130477184)]

sage: factor(1120228314932443982452255202016^2 + 2472109092323644501221860856287^2)
5^20 * 13^20 * 17^20