20090204, 12:02  #1 
Mar 2004
3·167 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? 
20090204, 12:15  #2  
Nov 2003
2^{2}×5×373 Posts 
Quote:
(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 20090204 at 12:15 Reason: fix bold 

20090204, 15:55  #3  
Mar 2004
3·167 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:


20090204, 18:45  #4  
Nov 2003
2^{2}×5×373 Posts 
Quote:
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, CantorZassenhaus, variations of ShanksTonelli, etc. 

20090311, 16:06  #5 
Feb 2005
2^{2}·3^{2}·7 Posts 
Just multiply n by any rth power root of 1 modulo N. In particular, if r is even, you can multiply n by 1 to get a different rth power root of k mod N.

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  20161021 22:21 
modular arithmetic  science_man_88  Miscellaneous Math  42  20110726 02:02 
need C/C++ modular arithmetic code for Windows  ixfd64  Programming  15  20080730 03:52 
Modular Arithmetic  Numbers  Math  27  20051130 15:41 
Jim Howell's modular arithmetic program?  ixfd64  Software  0  20040527 05:42 