Talk:Primitive root modulo n

Latest comment: 1 year ago by Herbmuell in topic Integers between 0 or 1 and n − 1 ?

An algorithm

edit

I am no expert on the subject, but as I am reading from Leveque, there is sort of an algorithm for finding primitive roots for higher powers of a prime when you already have a primitive root for odd p

let g be an integer, such that g mod p generates all elements of the field mod p, except zero

now either   is not divisible by   and then g mod   will be a primitive root for  if it is divisible by   , just take g+p and that will be a generator mod   what do you think?

Evilbu 21:43, 15 February 2006 (UTC)Reply

I'm not sure what the question is. If this is a theorem given by Leveque, its certainly appropriate to add it to the article. If this theorem has a name, that's even better: the section gets called 'so-and-so's theorem'. If you are saying "I just discovered a new algorithm; is it correct?" then I'll say "I don't know if its correct", and "don't add it to the article". linas 22:27, 15 February 2006 (UTC)Reply


Well Leveque first proves this theorem of how orders mod p and mod p^n on an integer are related. Next he just says and this implies existence of primitive root, just do this. He doesn't make a fuss about the construction, it has no name, it's just part of his proof of existence of primitive root.

Another thing I forgot, and I am quite sure of this, when x (integer) is mod p^n a primitive root, then, if x is odd, it is also such for mod p^n,and otherwise x+p^n will be a primitive root mod p^n

that way it really comes down to finding primitive roots mod p?

Evilbu 22:47, 15 February 2006 (UTC)Reply

This is a kind of Hensel's lemma application, I think. You can refine a 'solution' mod p to mod p2. etc. The lemma is Newton's method, really, while this case is simple enough to do directly. Charles Matthews 23:04, 15 February 2006 (UTC)Reply

Algorithms

edit

In order to make algorithms such as the number-theoretic transform work, one has to compute, in practice, a nth root of the unit in Z/pZ where n divides p-1, and n is most often a power of two. This is done easily provided one has a generator of Z/pZ*. Thus, it would be interesting to discuss algorithms for finding this generator, or primitive roots. David.Monniaux 08:31, 14 October 2006 (UTC)Reply

Probabilistic? Assuming one has factorised p − 1 already?. The chance that 2, or 3, or 5 is a primitive root is not small. Charles Matthews 12:19, 14 October 2006 (UTC)Reply
For the cases I'm interested in p is likely to be in the range of 264 at most, so it will be easily factorizable. Do you suggest I factor p, then compute φ(p), try kφ(p) for such values of k as 2, 3 or 5, then check for ke where e is a divisor of φ(p)? Er... It may work, indeed! David.Monniaux 13:46, 14 October 2006 (UTC)Reply
Yes, this might be practical. According to Artin's conjecture on primitive roots, 2 is a primitive root with a probability like 37%. And in most cases where you are unlucky it is because 2 is a quadratic residue mod p, which is a trivial calculation for rejection, as I guess you know, and will affect 50% of choices. Charles Matthews 16:36, 14 October 2006 (UTC)Reply

Bad encyclopedia article

edit

The article makes no sense to anyone other than math grads who wouldn't be looking in an encyclopedia for a definition in the first place.

It needs drastically rewriting. --86.143.198.23 20:35, 12 April 2007 (UTC)Reply

I added an example for laypeople. --68.219.18.137 (talk) 13:24, 4 January 2010 (UTC)Reply



The article is still poorly written. Wikipedia is another form of encyclopedia, not a textbook or research
publication. Therefore, all definitions of non-common terms should be given within the article or linked
to proper resources. What's the point to discuss minor improvements to the text, if very few of us can
get even though "introduction"?

For example, gcd(a, n) should be spelled out and linked to the corresponding article on Wikipedia,
simply because we all know what "greatest common denominator" is, but only few aware of "gcd".

--12.53.204.203 (talk) 19:02, 17 September 2010 (UTC)Reply

Agreed, it lost me before I got past the first line - a lot of Wikipedia "math" pages are like this, in fact, a lot of Wikipedia in general is heading this way which is a shame; particularly because it used to be somewhere the mathematically challenged could come. —Preceding unsigned comment added by 86.22.34.73 (talk) 15:29, 2 May 2011 (UTC)Reply

Precision about modulo

edit

In the second sentence, I think it should read "[...] the numbers coprime to n, taken modulo n, form a group with multiplication modulo n as the operation [...]" ?

Also, the 'Coprime' article could probably use the same addition, this time for the multiplication part.

86.198.94.108 16:45, 3 August 2007 (UTC) chromaninReply

Is this possibly why the example used in the article doesn't actually make sense?
30 mod 7 = 1 mod 7 = 1
31 mod 7 = 3 mod 7 = 1, because (3 x 2) + 1 = 7. Does someone have another way to explain why 3 is primitive root of 7?

Angwe (talk) 04:27, 19 August 2010 (UTC)Reply

Standard notation for index

edit

The article states that ν(a) is the standard notation for the index of a but I have only seen ind(a). This was used in both Planet Math and the 1911 Encyclopedia Britannica. Can someone give a reference for the ν notation? Otherwise I vote for using ind.--RDBury (talk) 15:27, 21 November 2008 (UTC)Reply

Davenport's Multiplicative Number Theory uses ν; I'm fairly sure that ind is a lot commoner. Virginia-American (talk) 19:16, 21 November 2008 (UTC)Reply
Pomerance & Crandall's Prime Numbers: A computational Perspective uses logg when discussing the discrete logarithm problem. (g is the primitive root). I don't recollect seeing this elsewhere.
The Wiki article should say something to the effect "commonly-seen notations are ..." or " there is no standard notation: different authors use different symbols. For example ..."
BTW, ν is potentially confusing, as νp(n) is often used for ordp(n), the exponenent of the highest power of p dividing n.
So is logg
Virginia-American (talk) 05:18, 22 November 2008 (UTC)Reply

Gauss's index table does not belong in this article

edit

Maybe Gauss's index table belongs in an article about discrete logarithms -- if such an article existed.

But it most assuredly does not belong in this article, where it is not directly relevant to the subject of this article.

Far more appropriate would be a goodly sized table of . . . primitive roots!!! The fact that primitive roots and discrete logarithms are related is no excuse -- everything in math is related, and even more so two concepts in the same subfield (number theory).

The table of Gauss's indexes is very poorly labeled. Its presence in this article is basically confusing. Its relevance to this article is not explained at all, and that's because it simply doesn't belong here.Daqu (talk) 23:27, 30 April 2009 (UTC)Reply


Euler's totient function

edit

I wonder why Euler's totient function is described by both   and  . Shouldn't this be the same function? —Preceding unsigned comment added by Enricorpg (talkcontribs) 00:44, 4 September 2009 (UTC)Reply

Fixed. Maxal (talk) 17:17, 19 August 2010 (UTC)Reply

Table of the smallest primitive roots

edit

The table is clearly wrong: for example, the smallest primitive root mod 13 is 2, not 6; the smallest primitive root mod 17 is 3, not 10; the smallest primitive root mod 19 is 2, etc. The OEIS link does give correct values in those cases. The table is also unsourced, and hence the information about the indices is questionable, and given that the first column is wrong, the whole thing appears to be OR.

Where did the table come from? I didn't have time to do extensive revision research, but the second edit by AxelBoldt actually listed the values of the smallest primitive roots correctly, and it stayed that way for a while. I think that the table should be replaced with the information from the OEIS just listing the smallest primitive roots. Arcfrk (talk) 20:48, 25 April 2012 (UTC)Reply

The first paragraph after the sub-head "Table of primitive roots" explains that this is not a table of smallest primitive roots; it is Gauss's table of primitive roots, which are chosen to given 10 the smallest index. So 6 is chosen as the listed primitive root for 13 because 62 = 10 mod 13, whereas 210 = 10 mod 13. I agree that placing the sentence linking to the OEIS sequence of smallest p.r.s just before the table was confusing - I have moved that sentence to after the table. Gandalf61 (talk) 12:00, 26 April 2012 (UTC)Reply

Simple algorithm for people trying to study?

edit

Me myself tried to get to this page to find a quick algorithm to solve if a is primitive root modulo p or to find an a that is a primitive root modulo p. After much work elsewhere I found that the algorithm might be quite simple and I thought this simple form might be here(correct me if I'm wrong though as I just barely learned this):

a is primitive root modulo p iff a^(p-1)/q != 1 (mod p), for each q<p-1, q|p-1

This is kinda the definition that I searched for anyways. — Preceding unsigned comment added by 89.233.235.80 (talk) 19:11, 30 August 2013 (UTC)Reply

The definition of primitive root

edit

The Camirael function of 15 is 4, and the order of 2, 7, 8, and 13 is also 4, why they are not primitive root mod 15?

If we change the definition of primitive root (as "values of m coprime to n which makes the maximum order mod n"), it is:

n primitive root order (OEISA002322)
1 0 1
2 1 1
3 2 2
4 3 2
5 2, 3 4
6 5 2
7 3, 5 6
8 3, 5, 7 2
9 2, 5 6
10 3, 7 4
11 2, 6, 7, 8 10
12 5, 7, 11 2
13 2, 6, 7, 11 12
14 3, 5 6
15 2, 7, 8, 13 4
16 3, 5, 11, 13 4
... ... ...
24 5, 7, 11, 13, 17, 19, 23 2
25 2, 3, 8, 12, 13, 17, 22, 23 20
... ... ...
30 7, 13, 17, 23 4

Is it right? (Also see OEISA111076 and OEISA046145)

What would be the point? We cannot take the name for something that is clearly defined (the primitive root) and repurpose it to something else (in this instance maximal-order elements). The purpose of an encyclopaedia is not to redefine terms. —Quondum 15:05, 9 October 2014 (UTC)Reply

However, the new definition will let all natural numbers have primitive root, it is wonderful! — Preceding unsigned comment added by 140.115.140.84 (talk) 08:51, 16 October 2014 (UTC)Reply

One of the most opaque articles I have ever seen

edit

The first paragraph of the "introductory" section of this article not only attempts to define "primitive root modulo n" but "discrete logarithm" as well in three sentences with an extremely high density of keywords and concepts that are beyond the realm of anyone without an advanced degree in math. Consequently, rather than shedding light on what a "primitive root modulo n" is, it leaves the reader more confused than before they started. Having to follow half a dozen links or more just to figure out what a sentence might possibly be saying is not a good way to gain an understanding of a subject.

When the "example for laypeople" was first added, the first four lines of the example were fairly obvious, but the reasons for choosing the congruent values "3 ×34 (mod 7)≡3 ×4" on the fifth line and "(33)2≡ 62 (mod 7)" on the sixth line were completely unobvious. In the current table, the choice of multiplicands in the fourth column appears nearly arbitrary: If the first two rows are results of 30 = 1 and 31 = 3, where do the 2 and 6 come from on the third and fourth rows, and why are 4 and 5 used on the last two rows where those are the exponents of the multiplicands in the third column?

Furthermore, when the "example for laypeople" was first added, the explanation "we see that the period is 6 because at 36 the modulus or remainder is once again 1" was reasonably explanitory: It included the reason why the period is 6. The current version's unadorned statement "we see that the period of 3k modulo 7 is 6" fails to include the enlightening phrase, contributing to the opaque nature of the article: The assertion may be obvious to mathematicians, but to someone seeking a better understanding, unreasoned statements from an "authority" leave the question "why?" unanswered.

With such an unhelpful "introductory" section and "Elementary Example" as the lead elements of the article, a reader has no incentive to continue through the rest of the piece, even if there may be better explanations later in its body. The entire page needs to be rewritten in a manner that starts with a general concept that is then developed and expanded with additional information as the article progresses.

FkoscharaApperian (talk) 21:53, 15 May 2015 (UTC)Reply

Gauss's index table

edit

The smallest primitive root of mod 71 is 7, the 24 primitive roots to mod 71 are 7, 11, 13, 21, 22, 28, 31, 33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 69, but why Gauss choose 62? Why not 7? — Preceding unsigned comment added by 101.14.37.23 (talk) 11:40, 21 August 2015 (UTC)Reply

Definition clarification

edit

I just want to clarify something. We know g is a primitive root modulo n IF every number "a" coprime to n is congruent to some number (g ^ k) mod n , where k could be any integer. Can we take "a" to be any integer, or do we need it to be in the set from 0 to n-1 (i.e. the multiplicative group of integers modulo n)?

For example, as in the example in the article, 3 is a primitive root modulo 7:

3^0 == 1
3^1 == 3
3^2 == 9
3^3 == 27
3^4 == 81
3^5 == 243
3^6 == 729
3^7 == 2187

1 mod 7 == 1
3 mod 7 == 3
9 mod 7 === 2
27 mod 7 == 6
81 mod 7 == 4
243 mod 7==5
729 mod 7==1
2187 mod 7==3

We see the solution set (1,3,2,6,4,5), then it repeats. That is, (1,2,3,4,5,6). If a is constrained to the multiplicative group of integers mod 7, a can be, coincidentally perfectly (I think?) 1,2,3,4,5, or 6:
0 coprime 7? no
1 coprime 7? yes
2 coprime 7? yes
3 coprime 7? yes
4 coprime 7? yes
5 coprime 7? yes
6 coprime 7? yes

But if a can be any integer at all, e.g. We know 8 is coprime to 7. Then 8 would not be congruent to any of the solutions, and so the requirement would not hold.


Can someone please clarify?

Update: Oh, I think I understand. Because we're working in mod 7: 8 mod 7 is 1, which then fits. In fact any number would fit the solution set except the ones that produce 0 from the mod operation (i.e. the multiples of 7), but we're covered there because 0 is not in the solution set.

Albatronix (talk) 00:23, 15 July 2018 (UTC)Reply


Example: primitive root mod prime

edit

Might be nice to include a prime mod (e.g. 13) within the Examples section. Currently, we have examples for 14 and 15 which don't show the "nicest" example where the congruence classes are {1, ..., p-1} but not every element is a primitive root.

Mateen Ulhaq (talk) 05:55, 25 July 2018 (UTC)Reply

If g is a primitive root modulo p, then g is also a primitive root modulo all powers unless gp−1 ≡ 1 (mod p2) in that case, g + p is.

edit

This needs an example. Because 2 ist a primitive root modulo 13 and   mod 169 ≡ 40   but if I calculate   mod 169 where t are all the numbers from 1 to 169 I do NOT get all the numbers from 1 to 168. EVERY MULTIPLE of 13 is missing!!!

Integers between 0 or 1 and n − 1 ?

edit

Quote: If n is a positive integer, the integers between 0 and n − 1 that are coprime to n (...) form a group, with multiplication modulo n as the operation; it is denoted by ×
n
, ...

Wouldn't it be better to say : ...the integers between 1 and n − 1... ? 0 is not coprime to n, 1 is.

I must unfortunately contradict myself a bit: If n = 1, then 0 and n are coprime (says uncle google), and ×
1
would appear to consist of the element 0. It looks strange, but is confirmed by φ(1) = 1 (the number of elements). Anyway, I would appreciate a comment from a mathematician.

Herbmuell (talk) 14:50, 20 March 2021 (UTC)Reply

Hi @Herbmuell: according to the definition of Coprime integers, 0 is technically coprime to 1, so to cover the case   we should include 0 in this set. This would also be consistent with the definition from Multiplicative group of integers modulo n:

the integers coprime (relatively prime) to n from the set   of n non-negative integers form a group under multiplication modulo n

Therefore I am changing it back to between 0 and  . Cheers
Burritok (talk) 18:45, 5 November 2022 (UTC)Reply
I don't agree with Burritok! 0 is NOT coprime to some n≥2, because gcd(0,2)=2≠1. But there is no harm at all in saying "IF every number a coprime to n is congruent to a power of g modulo n", because of the IF – and there may also be numbers ≠0 which are not coprime to n.
There is a bit of a grammatical ambiguity here: "the integers between 0 and n − 1 that are coprime" is intended to mean "of these integers from 0 to  , take the ones that are coprime to  ," rather than, "take these integers from 0 to  , all of which are coprime to  ." You're right 0 is not coprime to any  , but it is still good to include in the definition because it might be coprime to some   (specifically, 1). Burritok (talk) 19:35, 5 November 2022 (UTC)Reply

Thanks for taking this up Burritok, I get your explanation, and your solution looks fine to me. And other people shouldn't leave comments without signing them. Herbmuell (talk) 07:03, 29 November 2022 (UTC)Reply

Where are the equations ?

edit

Quote: ... emphasizing its role as a fundamental solution of the Root of unity modulo n polynomial equations Xm
− 1 in the ring n.

It looks wrong. Herbmuell (talk) 17:29, 20 March 2021 (UTC)Reply

The prominence of Gauss's historical table: bad idea

edit

Gauss's table should not be given the prominence that is is given in this article. In fact, it does not belong in this article at all.

It is distracting, not relevant to the point of this article, and on top of that it is very poorly explained and labeled. 2601:200:C000:1A0:5D0F:5849:9630:3ACF (talk) 18:24, 9 June 2021 (UTC)Reply

I agree - the table clutters the article and it is not clear to me why it is important, so I am going to be bold and delete it along with its section. If someone else thinks the table is important, I would advise simply including the essential information about it and an external link to the full table. If the table is really important, it may merit its own article ;) Burritok (talk) 19:15, 5 November 2022 (UTC)Reply