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

Thread Tools
Old 2019-02-10, 10:30   #1
Mar 2017

111102 Posts
Default 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(a-b, 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!
mathPuzzles is offline   Reply With Quote
Old 2019-02-10, 14:43   #2
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

22·769 Posts

I suggest looking here.
Dr Sardonicus is online now   Reply With Quote
Old 2019-02-12, 23:10   #3
Mar 2017

2×3×5 Posts

Originally Posted by Dr Sardonicus View Post
I suggest looking here.
Thanks for the hint!
So in my problem it seems like my roots a and b are called "primative modular n-th roots of unity" and I would refer to a sets as "a multiplicative ring of derived modular n-th 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(a-b, 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)

mathPuzzles is offline   Reply With Quote

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 2017-01-19 20:22
Basic Number Theory 15: Lagrange's theorem, cyclic groups and modular arithmetic Nick Number Theory Discussion Group 0 2017-01-07 13:15
Basic Number Theory 5: rationals & intro to modular arithmetic Nick Number Theory Discussion Group 1 2016-10-21 22:21
Extremely basic questions schwerlin Information & Answers 6 2015-01-20 19:26
Basic ECM questions VictordeHolland Information & Answers 5 2013-09-04 01:47

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

Thu Apr 9 21:12:52 UTC 2020 up 15 days, 18:45, 1 user, load averages: 1.94, 1.66, 1.58

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.