mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2020-10-31, 03:35   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

32×41 Posts
Default 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
bhelmes is offline   Reply With Quote
Old 2020-10-31, 11:48   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

2×3×293 Posts
Default

Quote:
Originally Posted by bhelmes View Post
How do I calculate 2. from 1. ?
It is not clear (to me anyway) where the 16 and 29 come from.
Nick is offline   Reply With Quote
Old 2020-10-31, 18:57   #3
bhelmes
 
bhelmes's Avatar
 
Mar 2016

32×41 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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
bhelmes is offline   Reply With Quote
Old 2020-11-01, 02:58   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

24×11×29 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2020-11-01, 09:25   #5
bhelmes
 
bhelmes's Avatar
 
Mar 2016

32×41 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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)



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


I understand that -i²=1



I appreciate your explications and patience.

Last fiddled with by bhelmes on 2020-11-01 at 09:26
bhelmes is offline   Reply With Quote
Old 2020-11-01, 09:51   #6
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

2·3·293 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
Nick is offline   Reply With Quote
Old 2020-11-01, 15:52   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

13F016 Posts
Default

Quote:
Originally Posted by bhelmes View Post
???
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.
Dr Sardonicus is offline   Reply With Quote
Old 2020-11-01, 20:00   #8
bhelmes
 
bhelmes's Avatar
 
Mar 2016

32·41 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post

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 ?


Thanks for your clear explications.
bhelmes is offline   Reply With Quote
Old 2020-11-01, 21:22   #9
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

24×11×29 Posts
Default

Quote:
Originally Posted by bhelmes View Post
Quote:
Originally Posted by Dr Sardonicus View Post

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.
Dr Sardonicus is offline   Reply With Quote
Old 2020-11-02, 18:40   #10
bhelmes
 
bhelmes's Avatar
 
Mar 2016

1011100012 Posts
Default

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
bhelmes is offline   Reply With Quote
Old 2020-11-02, 19:04   #11
sarahk99
 
Oct 2020

110 Posts
Default

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
sarahk99 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
runtime for the calculation of a quadratic residue bhelmes Number Theory Discussion Group 3 2020-10-17 13:37
Primorial calculation FreakyPotato Programming 7 2015-02-06 10:33
GHZ-days calculation Q tcharron PrimeNet 4 2014-06-27 23:27
mod p calculation help kurtulmehtap Math 3 2010-10-11 15:02
CPU Credit Calculation storm5510 Software 8 2009-09-25 21:06

All times are UTC. The time now is 08:21.


Sat Nov 27 08:21:17 UTC 2021 up 127 days, 2:50, 0 users, load averages: 2.18, 1.48, 1.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.