4

For any odd prime $p$ there exists at least one prime $q < p$ such that $q$ is a primitive root $\text{mod } p$ ; is this true?

Edward Jiang
  • 3,670
201044
  • 279
  • I recommend you read this page: http://mathworld.wolfram.com/PrimitiveRoot.html then come back and let us know if you're still unsure. – Robert Soupe Dec 20 '14 at 02:26
  • Without additional assumptions (GRH) the question is currently open. Please see this. – André Nicolas Dec 20 '14 at 03:20
  • @RobertSoupe: André Nicolas' comment suggests that OP will still be unsure. – daniel Dec 20 '14 at 06:23
  • This question has a simple solution, I think. Say all the primes < = p are Q(1) to Q(n) where n='phi'(p-1). Any residue R = [(Q(1)^A(1))(Q(2)^A(2))..(Q(n)^A(n))] mod(p) where A(i) are elements of integers. If each Q(i) prime < p is not a primitive root then for any i , (Q(i)^((p-1)/2)) = 1 mod(p). Therefore R^((p-1)/2) = 1 mod(p) for any residue R | 1 < R < (p-1). This contradiction proves the initial assertion. – 201044 Dec 24 '14 at 05:32
  • Let all primes < p be q(1) to q(n) where n = $\phi{p-1}$. Any residue R= ($\q(1)^a(1)$) – 201044 Jan 09 '15 at 00:07
  • I'm having trouble with your writing system. – 201044 Jan 09 '15 at 00:34
  • Assume for any prime q < p , q is not a primitive root mod(p). The order of q mod p being (p-1)/ T(q) where T(q) > = 2. If T(q) is even then q^((p-1)/2) = 1 mod(p) ; q would be a quadratic residue. If T(q) is odd then q^((p-1)/(2 T(q)) = -1 mod(p) so q^((p-1)/2) = -1 mod(p) and q would be a quadratic non-residue. So if the number of primes < p that are quadratic non=residues is even then the product of all these primes being W , w^((p-1)/2) = 1 mod(p). So some of the primes < p are quadratic res. and some are quadratic non-res. Is this all true? – 201044 Jan 09 '15 at 04:14
  • I made a mistake, what I wrote above does not prove the assertion. If all the primes less than p are not primitive roots mod p ; the ones that are quadratic non-residues, say Q(1) to Q(n) , each Q(i)^((p-1)/2) = -1 mod p. For any W | 1 < W < p ;W as an integer ( and not part of a congruence equation) is equal to the product of exponents of the primes less than p in a unique way. IF the number of primes less than p (in this representation of W) that are quadratic non-residues is even then W^((p-1)/2) = 1 mod p. W is a quadratic residue. – 201044 Jan 22 '15 at 05:16
  • Any prime Q < p that is not a primitive root and is a quadratic non-residue there exists t | Q^((p-1)/t) = 1 mod p, order of q mod p being (p-1)/t. If 2 | t then Q^((p-1)/2) = 1 mod p. This contradiction shows t is odd. If q is an odd prime and q | t then Q^((p-1)/q) = 1 mod p. – 201044 Jan 22 '15 at 05:25

0 Answers0