**HP Prime and HP 41C/DM 41L: Sum of Two Squares**

**Introduction**

Given a positive integer n, can we find two non-negative integers x and y such that:

n = x^2 + y^2

(x and y can be 0, n is assumed to be greater than 0)

There are several theorems and lemmas that are connected to this famous problem. As a point of interest, I will briefly describe them here.

1. n does not have a representation (n can't be written as x^2 + y^2) if any of n's prime factors is congruent to 3 mod 4 and is raised to an odd power.

2. If n has a representation, then for an integer k, k^2*n also has a representation.

3. If n is prime and congruent to 1 mod 4, then n has a representation. (n has the form of n = 4w + 1 for some non-negative integer w).

The program presented here is the use of iterations to find all possible pairs which fit n = x^2 + y^2. Some integers do not have representations, others have more than one. The program will show all possible combinations.

**HP Prime Program SUM2SQ**

EXPORT SUM2SQ(n)

BEGIN

// EWS 2019-07-21

// breaking n into a sum of 2 squares

LOCAL r,j,k,l;

// we can more than 1 representation

r:=IP((n/2)^0.5);

l:={};

FOR j FROM 0 TO r DO

k:=(n-j^2)^0.5;

IF FP(k)==0 THEN

l:=CONCAT(l,

{STRING(j)+"^2 + "+

STRING(k)+"^2 = "+

STRING(n)});

END;

END;

RETURN l;

END;

**HP 41C/DM 41L Program SUMSQRS**

Registers used:

R00 = n

R01 = counter

R02 = temporary

01 LBL T^SUMSQRS

02 FIX 0

03 STO 00

04 2

05 /

06 SQRT

07 INT

08 1000

09 /

10 STO 01

11 LBL 00

12 RCL 00

13 RCL 01

14 INT

15 X↑2

16 -

17 SQRT

18 STO 02

19 FRC

20 X=0?

21 GTO 01

22 GTO 02

23 LBL 01

24 RCL 01

25 INT

26 T^X =

27 ARCL X

28 AVIEW

29 STOP

30 RCL 02

31 T^Y =

32 ARCL X

33 AVIEW

34 STOP

35 LBL 02

36 ISG 01

37 GTO 00

38 T^END

39 VIEW

40 FIX 4

41 RTN

**Examples**

Example 1: n = 325

325 = 1^2 + 18^2

325 = 6^2 + 17^2

325 = 10^2 + 15^2

Example 2: n = 530

530 = 1^2 + 23^2

530 = 13^2 + 19^2

Source:

Dudley, Underwood. "Elementary Number Theory" 2nd Ed. Dover Publications: New York. 1978. ISBN 978-0-486-46931-7

All original content copyright, © 2011-2019. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.

## No comments:

## Post a Comment