20210610, 00:44  #1 
Mar 2016
2^{4}×3×7 Posts 
how do I find a and b with a²+b²=1 mod f
A peaceful and pleasant night for you,
how do I find (fast ?) a gaussian number a+bi with a²+b²=1 mod f where f is an odd number. Perhaps this question might be interesting also for others. A link or some keywords would be helpful. Last fiddled with by bhelmes on 20210610 at 00:45 
20210610, 01:05  #2 
"Robert Gerbicz"
Oct 2005
Hungary
10111000110_{2} Posts 
a+b*I=1 looks like good for every f.

20210610, 09:07  #3 
"Viliam Furík"
Jul 2018
Martin, Slovakia
541 Posts 
Well, you know Pythagorean triples, right? They satisfy a^{2} + b^{2} = c^{2}. When both sides are divided by c^{2}, we are left with (a/c)
^{2} + (b/c)^{2} = 1. So the rational points on the circle described by x^{2} + y^{2} = 1 are simply reduced Pythagorean triples. Thus for any Pythagorean triple (you can find a quick formula for them on Wikipedia) you reduce it and find one such point in the plane. You can extend these points infinitely far, by setting the righthand side of the equation to k*f + 1, say f is 3, and k is 2, then the number is 7, and multiplying the coordinates of the point on the unit circle by the square root of the number. For example: 3,4,5  Smallest Pythagorean triple (3/5)^{2} + (4/5)^{2} = 1 (sqrt(7)*3/5)^{2} + (sqrt(7)*4/5)^{2} = 1 (mod 3) There are other points on the unit circle, obviously, but those are irrational, so not as easy to find them all as rational points. But, you can extend any one of them (both the rational and irrational) by this method. So for given modulo f, you get the set of circles (sqrt(k*f+1)*x)^{2} + (sqrt(k*f+1)*y)^{2} = 1 (mod k*f+1), for k from 0 to inf. Finding a point on a unit circle is thus a pretty easy task, I think. You can basically brute force it: Choose any real number between 0 and 1, find its other coordinate on respective point on the unit circle, and extend to infinity and beyond. 
20210610, 12:43  #4  
Feb 2017
Nowhere
10764_{8} Posts 
Quote:
If f has more than one prime factor, there will be other solutions to y^2 == 1 (mod f), giving other solutions where one of a and b is 0 (mod f). Assuming you want 0 < a < f, 0 < b < f, you are out of luck if f = 3 or 5. If f > 5, one way might be to find some prime p congruent to 1 (mod 4) which does not divide f. [This should not take very long if you just try them in increasing order  5, 13, 17, 29, 37,... .] Let [c, d] = qfbsolve(Qfb(1,0,1),p) Compute e = znorder(Mod(p,f)). Then p^e is congruent to 1 (mod f), and a + b*I = (c + d*I)^e. [This could be done mod f, and the results lifted to give a and bvalues less than f if desired. If one of these reduces to 0 (mod f), try again.] Another possibility is to find a prime p congruent to 1 (mod 4*f). Then qfbsolve((Qfb(1,0,1),p) gives a solution. This could be reduced mod f if desired. If one of them is 0 (mod f), try again. However, I don't know how quickly one might find such a prime p. I have no idea how many tries might be required for either method to assure success, but I am pretty sure that for odd f > 3 there are solutions to x^2 + y^2 == 1 (mod f) with Mod(x,f) and Mod(y,f) both nonzero. Last fiddled with by Dr Sardonicus on 20210610 at 22:19 Reason: Insert omitted case 

20210611, 02:32  #5 
Mar 2016
101010000_{2} Posts 
Thanks a lot for all replies.
Is this a mathematical correct way: 1. Choose a,b with a>0 and b>0 and a=/=b and a²+b² =/=0 mod f (the trivial solutions are not important for me) 2. Set tan (alpha)=a/b 3. Double the angle with tan(2*alpha)=2/[cot(alpha)  tan (alpha)] = A/B 4. then sin (2*alpha)=A/(a²+b²) and cos (2*alpha)=B/(a²+b²) 5. Calculate a'= A*(a²+b²)⁻¹ mod f and b'=B*(a²+b²)⁻¹ mod f 6. (a')² + (b')²=1 mod f Correct ? 
20210612, 15:03  #6  
Feb 2017
Nowhere
1000111110100_{2} Posts 
Quote:
In (1), a^2 + b^2 =/= 0 (mod f) is not sufficient to insure that a^2 + b^2 has a multiplicative inverse (mod f). I leave the determination of the appropriate condition as an exercise. Assuming a^2 + b^2 has a multiplicative inverse (mod f), then (2*a*b*(a^2 + b^2)^(1))^2 + ((b^2  a^2)*(a^2 + b^2)^(1))^2 == 1 (mod f) is valid. If the a and b you have chosen do not satisfy the condition, you need to keep trying until you find a pair that does. 

20210613, 08:51  #7 
Jan 2020
3·11 Posts 
With your "trigonometric" approach, you use integer parameters a and b to build a Pythagorean triplet A,B,C:
A = 2*a*b, B = b^2  a^2, C = a^2 + b^2. Then you generate a candidate solution: x = A*(C^1) mod f, y = B*(C^1) mod f, where, like Dr. Sardonicus, I understand the operation "C^1" as computing the multiplicative inverse of C modulo f, which exists if and only if C is coprime with f. In order to emphasize this dependency from f, I'll write it as "modinv(C,f)". You also ask to avoid "trivial" solutions; let's define a solution (x,y) "trivial" if x^2 == 0 mod f and y^2 == 1 mod f, or if y^2 == 0 mod f and x^2 == 1 mod f. What about the conditions you gave at point (1)? For a given odd integer f, a "legal" starting choice (a,b) may fail to generate a solution: f = 25, a = 1, b = 3, C = 10, modinv(10,25) doesn't exist Or it may generate an unwanted trivial solution: f = 7, a = 3, b = 4, C = 25, modinv(25,7) = 2, x = 24*2 = 48 == 6 mod 7 y = 7*2 = 14 == 0 mod 7 But, if f is coprime with 15, your "Pythagorean" construction provides a nontrivial solution at the very first choice a = 1, b = 2: x = 4*modinv(5,f) y = 3*modinv(5,f) We can easily see that it's nontrivial because the eight numbers 3, 4, 5, modinv(5,f), x, y, x^2, y^2 are all coprime with f. Example with f = 7: modinv(5,7) = 3 x = 4*3 = 12 == 5 mod 7 y = 3*3 = 9 == 2 mod 7 5^2+2^2 = 29 == 1 mod 7 Now suppose that f is not coprime with 15, but it has at least two distinct prime divisors, so that we can "factor" f as g*h, with gcd(g,h) = 1. Let's try another kind of construction. By chinese remainder theorem, the following system of congruences is solvable: x == 0 mod g x == 1 mod h y == 1 mod g y == 0 mod h We can see that we get a nontrivial solution because: congruence x^2+y^2 == 1 holds modulo g and modulo h, so also modulo g*h congruence x^2 == 0 holds modulo g but not modulo h, so not modulo g*h congruence y^2 == 0 holds modulo h but not modulo g, so not modulo g*h Example with f=15, g=3, h=5: x == 0 mod 3 and x == 1 mod 5, so x == 6 mod 15 y == 1 mod 3 and y == 0 mod 5, so y == 10 mod 15 6^2+10^2 = 136 == 1 mod 15 Together, the "Pythagorean" and "Chinese" constructions cover all odd numbers f, excluding the prime powers of the form f=3^n or f=5^n. For these cases, we can use Hensel lifting. Given a solution (x,y) for f = p^n, we can build a solution (x,y') for f' = p^(n+1) as follows. Consider the quadratic congruence: x^2 + y'^2 == 1 mod p^(n+1) after the substitutions: y' = y + R*p^n x^2 + y^2 = 1 + Q*p^n and some simplifications, we obtain the linear congruence: Q + 2*y*R == 0 mod p which can be easily solved: R == Q*modinv(2*y,p) mod p Example: prime powers of the form 3^n. for n = 1, two solutions, all trivial: (0,1) (0,2) for n = 2, six solutions, all trivial: (0,1) (0,8) (3,1) (3,8) (6,1) (6,8) for n = 3, twelve nontrivial solutions, including (3,10) and (3,17) Lifting only them, we obtain: for n=4, solutions (3,37) and (3,44) for n=5, solutions (3,199) and (3,44) and so on. 
20210615, 00:30  #8 
"Matthew Anderson"
Dec 2010
Oregon, USA
2×397 Posts 
Hi again,
Four solutions that come to mind are { 1, 1, i, and i} not a complete set. Matt 
20210615, 13:01  #9 
Feb 2017
Nowhere
2^{2}·3·383 Posts 
If f = q, a prime number, the number of solutions to x^2 + y^2 = 1 (mod q) may be counted as follows:
Note that 1 + (a/q) or 1 + kronecker(a,q) is 2 if a is a quadratic residue (mod q), 0 if a is a quadratic nonresidue (mod q), and 1 if a == 0 (mod q). Then (1 + (r/q))*(1 + ((1r)/q)) =
Thus we get a contribution of 4 for each nontrivial solution, and a contribution of 2 for each of (r, 1  ) = (0,1) and (1, 0). Now (1 + (r/q))*(1 + ((1r)/q)) = 1 + (r/q) + ((1  r)/q) + (r*(1r)/q) Let n be the number of nontrivial solutions. Summing on all r (mod q) we have 4*n + 4 = q + 0 + 0 + where J is a Jacobi sum, and is the quadratic character (a/q). Since this character is selfinverse, the Jacobi sum evaluates to (1/q). Thus 4*n + 4 = q (1/q), or n = (q  (1/q))/4  1. This formula gives n = 0 for q = 3 or 5, but n > 0 for q > 5. EDIT: Pursuant to a PM from a discerning reader, I have changed the name of the arbitrary residue (mod q) from "a" to r. My previous usage of "a" was confusing since it is used in the subject to denote a root of one of the squares. The above formula counts the number of pairs of squares (a^2, b^2) (mod q) for which a^2 + b^2 == 1 (mod q). Determining the corresponding number of distinct pairs (a, b) is a bit involved. For any pair of roots (a, b) we can, by replacing a by q  a or b with q  b if necessary, and reordering the pair if necessary, assume that 0 <= a <= b < q/2. By changing signs and reordering this pair, we can nominally produce eight "equivalent" pairs. But if a = 0 or a = b, that number goes down. I'm too lazy to work out the details. Last fiddled with by Dr Sardonicus on 20210621 at 12:36 Reason: missing equals sign; awkward phrasing; add clarification 
20210617, 13:19  #10 
Feb 2017
Nowhere
2^{2}·3·383 Posts 
Let f > 1 be an odd integer. The set of Gaussian integers mod f,
Mod(a,f) + Mod(b,f)*I for which Mod(a^2 + b^2, f) = Mod(1, f) forms a subgroup of the multiplicative group (Z[I]/f)^{*} of invertible elements of Z[I]/f . Taking a prime p == 1 (mod 4) which does not divide f, and x^2 + y^2 = p, we have that Mod(x^2 + y^2, f) is invertible, so that the "trigonometric solution" is valid: a = Mod(2*x*y/(x^2 + y^2), f), b = Mod((x^2  y^2)/(x^2 + y^2), f). I note that for f > 5, the smallest p satisfies p < f, so that a and b are both nonzero residues (mod f) [however, for f = 9 or 25, a^2 or b^2 is 0 (mod f)]. By replacing a by f  a or b with f  b if necessary, we can assume that 0 < a < f/2 and 0 < b < f/2. The smallest f > 5 requiring p > 5 is f = 15, as do f = 15 + 10*k; the smallest f requiring p > 13 is f = 5*13 = 65, as do f = 5*13 + 10*13*k; the smallest f requiring p > 17 is f = 5*13*17, as do 5*13*17 + 10*13*17*k, and so on. For f = 27, taking the "trigonometric solution" using p = 5 gives a = Mod(44, 27), b = Mod(33, 27) which give a = 17, b = 6. One can take a = 27  17 = 10 < 27/2; 10^2 + 6^2 = 136 = 27*5 + 1 For f = 125, p = 13 gives a = Mod(924,125) and b = Mod(385, 125) or a = 49, b = 10; 49^2 + 10^2 = 2501 = 125* 20 + 1. 
20210620, 00:24  #11 
Mar 2016
2^{4}·3·7 Posts 
A peaceful and pleasant night for you,
For people who like phpscripts I added a calculator which decline from the pyth. trippel to the gaussian integer modulo f: http://devalco.de/System/system_one_complex_pyth2.php I noticed that this transformation is surjectiv. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Where can I find a Reverse and Add program? I can't find any!  Stargate38  Programming  18  20150710 06:08 
Find the Value  davar55  Puzzles  7  20090702 19:46 
Find the Value  davar55  Puzzles  25  20070715 15:56 
New way to Find (X^Y) % M  maheshexp  Miscellaneous Math  29  20040830 15:59 
New way to Find (X^Y) % M  maheshexp  Software  2  20040508 03:16 