20190210, 10:30  #1 
Mar 2017
2·3·5 Posts 
Basic questions about modular roots
We have an nth root of unity modulus a composite C. So \(a^n \equiv 1 \mod C, a\ne 1\). Since \(a\) is a root, so is \(a^2, a^3, a^4 \ldots\) until the list cycles back to \(a\) in at most \(n\) entries.
Since C is composite, the roots in that list are not all the possible roots, there can be another root \(b\) which is not in that enumerated set, and it has its own list of derivative roots \(b, b^2, b^3, b^4 \ldots\). What is the vocabulary word that discribes these kinds of sets? Something like "derived roots of a" or something. If n is 2, you could probably use the word "conjugates" for a pair of roots. I want to be able to write something like "If \(C=pq\) then we need one characteristic root from two different (superconjugate sets??) to be able to enumerate all of the n'th roots of unity." without making up my own vocabulary and overly amusing real mathematican readers. Second question is regards to the number theory of roots itself. I've seen it stated in descriptions of factoring algorithms that if we have two such sets of roots and do indeed know a characteristic root from each set, then GCD(ab, C) will reveal p or q as a factor of C. I can test this experimentally, but I have not been able to derive it. What's the strategy? I suspect it's very elementary and I just have a mental block about the direction to take to crack it. Thanks for any help! 
20190212, 23:10  #3  
Mar 2017
2×3×5 Posts 
Quote:
So in my problem it seems like my roots a and b are called "primative modular nth roots of unity" and I would refer to a sets as "a multiplicative ring of derived modular nth roots". How would I state the fact that the two rings share 1, but are otherwise disjoint? ie, a and b are special in that one is not a power of the other (or it'd be in that ring). Next I need to tackle the GCD(ab, C) finding a factor of C conjecture. I'm no longer certain it's true, and maybe it just works in some random cases (common when C is small) Thanks! 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Basic Number Theory 16: unit group structure in modular arithmetic  Nick  Number Theory Discussion Group  0  20170119 20:22 
Basic Number Theory 15: Lagrange's theorem, cyclic groups and modular arithmetic  Nick  Number Theory Discussion Group  0  20170107 13:15 
Basic Number Theory 5: rationals & intro to modular arithmetic  Nick  Number Theory Discussion Group  1  20161021 22:21 
Extremely basic questions  schwerlin  Information & Answers  6  20150120 19:26 
Basic ECM questions  VictordeHolland  Information & Answers  5  20130904 01:47 