mersenneforum.org > Math calculation of the non quadratic residium
 Register FAQ Search Today's Posts Mark Forums Read

 2020-10-31, 03:35 #1 bhelmes     Mar 2016 32·41 Posts calculation of the non quadratic residium A peaceful and pleasant night for you, I know that from the pyth. trippel (3, 4, 5) - > 3/5, 4/5 mod 61 = (13+25i) 1. and that (13+25i)^30 = 1 mod 61 2. and |16+29i| = (16²+29²) = -1 mod 61 which is a non quadratic residium How do I calculate 2. from 1. ? Thanks in advance if someone knows a good answer or a link. Last fiddled with by bhelmes on 2020-10-31 at 03:52
2020-10-31, 11:48   #2
Nick

Dec 2012
The Netherlands

3×587 Posts

Quote:
 Originally Posted by bhelmes How do I calculate 2. from 1. ?
It is not clear (to me anyway) where the 16 and 29 come from.

2020-10-31, 18:57   #3
bhelmes

Mar 2016

32×41 Posts

Quote:
 Originally Posted by bhelmes A peaceful and pleasant night for you, I know that from the pyth. trippel (3, 4, 5) - > 3/5, 4/5 mod 61 = (13+25i) 1. and that (13+25i)^30 = 1 mod 61 2. and |16+29i| = (16²+29²) = -1 mod 61 which is a non quadratic residium How do I calculate 2. from 1. ?

(16+29i)²=(25+13i) mod 61
(25+13i) can be mirrored at the main diagonale,
so that the point of the unit circle (13+25i) "=" (25+13i)

tan (alpha)=3/4, tan (alpha/2)=(5-4)/3=1/3 if this helps

I want to calculate the non quadratic residium of (25+13i) mod 61,
but i do not know how.

Last fiddled with by bhelmes on 2020-10-31 at 18:58

2020-11-01, 02:58   #4
Dr Sardonicus

Feb 2017
Nowhere

5,147 Posts

Quote:
 Originally Posted by bhelmes 1. and that (13+25i)^30 = 1 mod 61
Pari-GP begs to differ:

Code:
? (Mod(13,61)+Mod(25,61)*I)^30

%1 = Mod(60, 61)
which is -1 (mod 61). You appear to have interchanged real and imaginary parts, which is equivalent to taking the conjugate, and then multiplying by I. We would thus have

(Mod(25,61)+Mod(13,61)*I)^30 = Mod(1,61).

Your question is complicated by the fact that, in the ring of Gaussian integers R = Z + Z*I, I2 = -1 (Pari-GP notation), 61 is not prime; 61R is not a prime ideal.

We have 61R = P1P2, where P1 = (5 + 6*I)R and P2 = (5 - 6*I)R are prime ideals.

The residue rings R/P1 and R/P2 are "different" copies of the finite field F61 = Z/61Z, the integers modulo 61.

A quadratic residue (mod 61R) is, presumably, a quadratic residue (mod P1) and (mod P2).

R/P1 may be described by mapping a + b*I to a - 11*b (a, b integers) and reducing this integer mod 61; for R/P2 map a + b*I to a + 11*b and reduce mod 61. Quadratic residues (mod 61R) are characterized by both integer modulo results being quadratic residues (mod 61). Getting from the two ordinary quadratic residues (mod 61) to a square root of your complex number (mod 61R) is a little involved, but can be done.

Doing the two mappings with 13 + 25*I gives Mod(43, 61) and Mod(44, 61), both quadratic non-residues. So 13 + 25*I is a quadratic non-residue (mod 61R).

However, with 25 + 13*I we get Mod(4, 61) and Mod(46, 61) which are both quadratic residues, so 25 + 13*I is a quadratic residue (mod 61R). And in fact,

(Mod(16, 61) + Mod(29,61)*I)2 = Mod(25,61) + Mod(13,61)*I.

2020-11-01, 09:25   #5
bhelmes

Mar 2016

32×41 Posts

Quote:
 Originally Posted by Dr Sardonicus Your question is complicated by the fact that, in the ring of Gaussian integers R = Z + Z*I, I2 = -1 (Pari-GP notation), 61 is not prime; 61R is not a prime ideal.

???
I think 61 is a prime ideal in the Gaussian integers,
61=(6+5i)(6-5i)

I understand that -i²=1

I appreciate your explications and patience.

Last fiddled with by bhelmes on 2020-11-01 at 09:26

2020-11-01, 09:51   #6
Nick

Dec 2012
The Netherlands

3·587 Posts

Quote:
 Originally Posted by bhelmes I think 61 is a prime ideal in the Gaussian integers, 61=(6+5i)(6-5i)
In any commutative ring R (such as the ordinary integers or the Gaussian integers),
• a non-zero element p generates a prime ideal if and only if p is a prime element
• all prime elements are irreducible
and the units in the Gaussian integers are just 1,-1,i and -i,.
Since 61=(6+5i)(6-5i), 61 is not irreducible in the Gaussian integers and therefore not prime, hence it does not generate a prime ideal.

2020-11-01, 15:52   #7
Dr Sardonicus

Feb 2017
Nowhere

5,147 Posts

Quote:
 Originally Posted by bhelmes ??? I think 61 is a prime ideal in the Gaussian integers, 61=(6+5i)(6-5i)
Then you are arguing with a definition. First, an ideal M in a commutative ring R is a subset of R which is

(a) closed under addition (if x and y are in M then so is x + y),

and

(b) closed under multiplication by all elements of the ring R; if r is any element of R, and x is in M, then r*x is also in M.

A prime ideal P in a commutative ring R is an ideal such that, if x and y are in R and x*y is in P, then x is in P or y is in P.

With R = Z + Z*i, neither x = 6 + 5*i nor y = 6 - 5*i is in 61R, but their product is. Therefore, by definition, 61R is not a prime ideal of R.

2020-11-01, 20:00   #8
bhelmes

Mar 2016

32·41 Posts

Quote:
 Originally Posted by Dr Sardonicus R/P1 may be described by mapping a + b*I to a - 11*b (a, b integers) and reducing this integer mod 61; for R/P2 map a + b*I to a + 11*b and reduce mod 61.

How do you calculate the mapping function ?

2020-11-01, 21:22   #9
Dr Sardonicus

Feb 2017
Nowhere

514710 Posts

Quote:
Originally Posted by bhelmes
Quote:
 Originally Posted by Dr Sardonicus R/P1 may be described by mapping a + b*I to a - 11*b (a, b integers) and reducing this integer mod 61; for R/P2 map a + b*I to a + 11*b and reduce mod 61.
How do you calculate the mapping function ?
Very simple: 11 and -11 are the square roots of -1 (mod 61).

The fact that 61R = P1P2 has consequences. Typically*, a square Mod(a,61) + Mod(b,61)*I has two square roots (mod P1) and two square roots (mod P2). Consequently, it will typically have four square roots mod 61R. For example, Mod(25,61) + Mod(13,61)*I has the square roots

Mod(16, 61) + Mod(29, 61)*I,
Mod(14, 61) + Mod(7, 61)*I,
Mod(45, 61) + Mod(32, 61)*I, and
Mod(47, 61) + Mod(54, 61)*I.

*The exceptional cases are left as an exercise for the reader.

 2020-11-02, 18:40 #10 bhelmes     Mar 2016 36910 Posts For mathematical curosity and practical use: Is it possible to calculate the square root of a quadratic residium by using the tangens function ? I have the pythagoraic tripple 11,60,61 (which indicates a rational point on the circle, tan (alpha)= 11/60, tan (alpha/2)=(61-60)/11 = 1/11 and 1=-i² 1/11 = (1+9*61) / 11 = 55 mod 61 But then I do not know ? Best regards Bernhard
2020-11-02, 19:04   #11
sarahk99

Oct 2020

1 Posts

Quote:
 Very simple: 11 and -11 are the square roots of -1 (mod 61). The fact that 61R = P1P2 has consequences. Typically*, a square Mod(a,61) + Mod(b,61)*I has two square roots (mod P1) and two square roots (mod P2). Consequently, it will typically have four square roots mod 61R. For example, Mod(25,61) + Mod(13,61)*I has the square roots Mod(16, 61) + Mod(29, 61)*I, Mod(14, 61) + Mod(7, 61)*I, Mod(45, 61) + Mod(32, 61)*I, and Mod(47, 61) + Mod(54, 61)*I. *The exceptional cases are left as an exercise for the reader.
sounds a little bit complicated to me

 Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Number Theory Discussion Group 3 2020-10-17 13:37 FreakyPotato Programming 7 2015-02-06 10:33 tcharron PrimeNet 4 2014-06-27 23:27 kurtulmehtap Math 3 2010-10-11 15:02 storm5510 Software 8 2009-09-25 21:06

All times are UTC. The time now is 10:01.

Wed Dec 8 10:01:35 UTC 2021 up 138 days, 4:30, 1 user, load averages: 2.25, 1.88, 1.66