mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-02-04, 12:02   #1
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

2·13·19 Posts
Default modular arithmetic problem

I can't remember one of the things I learned in algebra class:

Given odd numbers N and r, suppose we know n is an rth root of k. Are there any general or special cases when we can find a different rth root of k?
JuanTutors is offline   Reply With Quote
Old 2009-02-04, 12:15   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by dominicanpapi82 View Post
I can't remember one of the things I learned in algebra class:

Given odd numbers N and r, suppose we know n is an rth root of k. Are there any general or special cases when we can find a different rth root of k?
Huh? The question makes ZERO sense.

(1) You have not specified the domain in which you are working.
(2) If you are working in the reals, only one such rth root ever exists.
(3) If you are working over C, then k always has r rth roots. What do
you mean by "special cases when we can find a different rth root"?
What do you mean by "find"??? Determining all of the r'th roots of k
is trivially given by DeMoivre's Theorem. This is high school level math.
(4) Your notation sucks. You use both N and n to mean the same thing.
Or, if you intend that they denote different numbers, then you have not defined N.

Last fiddled with by R.D. Silverman on 2009-02-04 at 12:15 Reason: fix bold
R.D. Silverman is offline   Reply With Quote
Old 2009-02-04, 15:55   #3
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

2·13·19 Posts
Default

Of course. Sorry, I didn't realize I didn't type mod N.

Restated correctly: Given odd numbers N and r, suppose we know n is an rth root of k mod N. Are there any general or special cases when we can find a different rth root of k mod N?

I think I know the answer to the question, but I wanted to verify it.

Quote:
Originally Posted by R.D. Silverman View Post
Huh? The question makes ZERO sense.

(1) You have not specified the domain in which you are working.
(2) If you are working in the reals, only one such rth root ever exists.
(3) If you are working over C, then k always has r rth roots. What do
you mean by "special cases when we can find a different rth root"?
What do you mean by "find"??? Determining all of the r'th roots of k
is trivially given by DeMoivre's Theorem. This is high school level math.
(4) Your notation sucks. You use both N and n to mean the same thing.
Or, if you intend that they denote different numbers, then you have not defined N.
JuanTutors is offline   Reply With Quote
Old 2009-02-04, 18:45   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by dominicanpapi82 View Post
Of course. Sorry, I didn't realize I didn't type mod N.

Restated correctly: Given odd numbers N and r, suppose we know n is an rth root of k mod N. Are there any general or special cases when we can find a different rth root of k mod N?

I think I know the answer to the question, but I wanted to verify it.
What do you mean by "find".

Sometimes, (many times) when r is odd, there is only one such root.

When there exists more than one, there are a variety of methods
to "find" them; e.g. Berlekamp, Cantor-Zassenhaus, variations of
Shanks-Tonelli, etc.
R.D. Silverman is offline   Reply With Quote
Old 2009-03-11, 16:06   #5
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by dominicanpapi82 View Post
Given odd numbers N and r, suppose we know n is an rth root of k mod N. Are there any general or special cases when we can find a different rth root of k mod N?
Just multiply n by any r-th power root of 1 modulo N. In particular, if r is even, you can multiply n by -1 to get a different r-th power root of k mod N.
maxal is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 5: rationals & intro to modular arithmetic Nick Number Theory Discussion Group 1 2016-10-21 22:21
modular arithmetic science_man_88 Miscellaneous Math 42 2011-07-26 02:02
need C/C++ modular arithmetic code for Windows ixfd64 Programming 15 2008-07-30 03:52
Modular Arithmetic Numbers Math 27 2005-11-30 15:41
Jim Howell's modular arithmetic program? ixfd64 Software 0 2004-05-27 05:42

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

Fri Oct 23 08:41:23 UTC 2020 up 43 days, 5:52, 0 users, load averages: 0.75, 1.14, 1.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.