calculation of the non quadratic residium

[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. ?


Thanks in advance if someone knows a good answer or a link.

[Nick]

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.

[bhelmes]

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.

[Dr Sardonicus]

Originally Posted by bhelmes

1. and that (13+25i)^30 = 1 mod 61

Pari-GP begs to differ:

? (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, I² = -1 (Pari-GP notation), 61 is not prime; 61R is not a prime ideal.

We have 61R = P₁P₂, where P₁ = (5 + 6*I)R and P₂ = (5 - 6*I)R are prime ideals.

The residue rings R/P₁ and R/P₂ are "different" copies of the finite field F₆₁ = Z/61Z, the integers modulo 61.

A quadratic residue (mod 61R) is, presumably, a quadratic residue (mod P₁) and (mod P₂).

R/P₁ may be described by mapping a + b*I to a - 11*b (a, b integers) and reducing this integer mod 61; for R/P₂ 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)² = Mod(25,61) + Mod(13,61)*I.

[bhelmes]

Originally Posted by Dr Sardonicus

Your question is complicated by the fact that, in the ring of Gaussian integers R = Z + Z*I, I² = -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)



http://devalco.de/poly_xx+yy_demo.ph...60&radius_c=61


I understand that -i²=1



I appreciate your explications and patience.

[Nick]

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.

[Dr Sardonicus]

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.

[bhelmes]

Originally Posted by Dr Sardonicus

R/P₁ may be described by mapping a + b*I to a - 11*b (a, b integers) and reducing this integer mod 61; for R/P₂ map a + b*I to a + 11*b and reduce mod 61.

How do you calculate the mapping function ?


Thanks for your clear explications.

[Dr Sardonicus]

Originally Posted by bhelmes

How do you calculate the mapping function ?

Very simple: 11 and -11 are the square roots of -1 (mod 61).

The fact that 61R = P₁P₂ has consequences. Typically^*, a square Mod(a,61) + Mod(b,61)*I has two square roots (mod P₁) and two square roots (mod P₂). 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.

[bhelmes]

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

[sarahk99]

Very simple: 11 and -11 are the square roots of -1 (mod 61).

The fact that 61R = P₁P₂ has consequences. Typically^*, a square Mod(a,61) + Mod(b,61)*I has two square roots (mod P₁) and two square roots (mod P₂). 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