Talk:Primitive root modulo n

An algorithm

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 $g^{p-1}-1$ is not divisible by $p^{2}$ and then g mod $p^{n}$ will be a primitive root for$p^{n}$ if it is divisible by $p^{2}$ , just take g+p and that will be a generator mod $p^{n}$ what do you think?

Evilbu 21:43, 15 February 2006 (UTC)

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)

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)

This is a kind of Hensel's lemma application, I think. You can refine a 'solution' mod p to mod p². 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)

Algorithms

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)

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)

For the cases I'm interested in p is likely to be in the range of 2⁶⁴ 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 k^e where e is a divisor of φ(p)? Er... It may work, indeed! David.Monniaux 13:46, 14 October 2006 (UTC)

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)

Bad encyclopedia article

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)

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

---

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)

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)

Precision about modulo

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) chromanin

Is this possibly why the example used in the article doesn't actually make sense?

3⁰ mod 7 = 1 mod 7 = 1

3¹ 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)

Standard notation for index

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)

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)

Pomerance & Crandall's Prime Numbers: A computational Perspective uses log_g 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 ord_p(n), the exponenent of the highest power of p dividing n.

So is log_g

Virginia-American (talk) 05:18, 22 November 2008 (UTC)

Gauss's index table does not belong in this article

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)

Euler's totient function

I wonder why Euler's totient function is described by both $\varphi (n)$ and $\phi \left(n\right)$. Shouldn't this be the same function? —Preceding unsigned comment added by Enricorpg (talk • contribs) 00:44, 4 September 2009 (UTC)

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

Table of the smallest primitive roots

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)

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 6² = 10 mod 13, whereas 2¹⁰ = 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)

Simple algorithm for people trying to study?

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)

The definition of primitive root

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 (OEIS: A002322)
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 OEIS: A111076 and OEIS: A046145)

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)

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)

One of the most opaque articles I have ever seen

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 ×3⁴ (mod 7)≡3 ×4" on the fifth line and "(3³)²≡ 6² (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 3⁰ = 1 and 3¹ = 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 3^k 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)

Gauss's index table

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)

Definition clarification

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)

Example: primitive root mod prime

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)

If g is a primitive root modulo p, then g is also a primitive root modulo all powers $p^{k}$ unless g^p−1 ≡ 1 (mod p²) in that case, g + p is.

This needs an example. Because 2 ist a primitive root modulo 13 and $2^{12}$ mod 169 ≡ 40 $\neq 1$ but if I calculate $2^{t}$ 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 ?

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 ℤ^×
₁ 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)

Hi @Herbmuell: according to the definition of Coprime integers, 0 is technically coprime to 1, so to cover the case $n=1$ 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 $\{0,1,\dots ,n-1\}$ of n non-negative integers form a group under multiplication modulo n

Therefore I am changing it back to between 0 and $n-1$. Cheers

Burritok (talk) 18:45, 5 November 2022 (UTC)

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 $n-1$, take the ones that are coprime to $n$," rather than, "take these integers from 0 to $n-1$, all of which are coprime to $n$." You're right 0 is not coprime to any $n>2$, but it is still good to include in the definition because it might be coprime to some $n$ (specifically, 1). Burritok (talk) 19:35, 5 November 2022 (UTC)

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)

Where are the equations ?

Quote: ... emphasizing its role as a fundamental solution of the Root of unity modulo n polynomial equations X^m
− 1 in the ring ℤ_n.

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

The prominence of Gauss's historical table: bad idea

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)

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)