 mersenneforum.org > Math modular arithmetic problem
 Register FAQ Search Today's Posts Mark Forums Read 2009-02-04, 12:02 #1 JuanTutors   "Juan Tutors" Mar 2004 10718 Posts 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?   2009-02-04, 12:15   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

5×1,493 Posts Quote:
 Originally Posted by dominicanpapi82 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   2009-02-04, 15:55   #3
JuanTutors

"Juan Tutors"
Mar 2004

10001110012 Posts 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 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.   2009-02-04, 18:45   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

5·1,493 Posts Quote:
 Originally Posted by dominicanpapi82 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.   2009-03-11, 16:06   #5
maxal

Feb 2005

11×23 Posts Quote:
 Originally Posted by dominicanpapi82 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.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 1 2016-10-21 22:21 science_man_88 Miscellaneous Math 42 2011-07-26 02:02 ixfd64 Programming 15 2008-07-30 03:52 Numbers Math 27 2005-11-30 15:41 ixfd64 Software 0 2004-05-27 05:42

All times are UTC. The time now is 05:06.

Sat Aug 20 05:06:02 UTC 2022 up 2 days, 2:34, 0 users, load averages: 1.65, 1.29, 1.21