[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

4.0. "Primes in A.P." by HARE::STAN () Fri Jan 20 1984 23:21

From:	ROLL::USENET       "USENET Newsgroup Distributor"  6-JAN-1984 22:13
To:	HARE::STAN
Subj:	USENET net.math newsgroup articles


              -------------------------------------------

Newsgroups: net.math
Path: decwrl!decvax!harpo!seismo!hao!hplabs!intelca!proper!chongo
Subject: Primes in Arithmetic Progression


Paul A. Pritchard of Cornell University reported the discovery of the
following progression of primes:

		107928278317 + k*9922782870  	for k=0,1,...,17

this 18 member sequence is the longest Arithmetic Progression known.

chongo <2,3,5,7,...> /\pp/\
T.RTitleUserPersonal
Name
DateLines
4.1raised from 18 to 21GUESS::DERAMODan D'EramoWed Jan 30 1991 15:5596
Path: ryn.mro4.dec.com!shlump.nac.dec.com!decuac!pa.dec.com!decwrl!sdd.hp.com!samsung!munnari.oz.au!csc.anu.edu.au!manuel!anucsd!neptune!pap
From: pap@neptune.anu.edu.au (Paul Pritchard)
Newsgroups: sci.math
Subject: 21 primes in arithmetic progression
Keywords: prime number
Message-ID: <pap.664585858@neptune>
Date: 22 Jan 91 23:10:58 GMT
Sender: news@anucsd.anu.oz.au (USENET News software)
Organization: ANU Department of Computer Science
Lines: 19
 
There is an arithmetic progression of 21 primes:
    142072321123 + 1419763024680 i, 0 <= i < 21.
 
It was discovered on 30 November 1990, by programs running in the background
on a network of Sun 3 workstations in the Department of Computer Science,
University of Queensland, Australia.
 
See: Andrew Moran and Paul Pritchard, The design of a background job
on a local area network, Procs. 14th Australian Computer Science Conference,
1991, to appear.
 
For a 1-page poster of this discovery, process the accompanying
posting with LaTeX.
 
--Paul Pritchard
  School of Computing and Information Technology
  Griffith University
  Nathan, Queensland, AUSTRALIA 4111
  [e-mail: pap@gucis.sct.gu.edu.au; FAX: +61 7 875 5198; phone: +61 7 875 5010]

Path: ryn.mro4.dec.com!shlump.nac.dec.com!rust.zso.dec.com!pa.dec.com!decwrl!sdd.hp.com!zaphod.mps.ohio-state.edu!samsung!munnari.oz.au!csc.anu.edu.au!manuel!anucsd!neptune!pap
From: pap@neptune.anu.edu.au (Paul Pritchard)
Newsgroups: sci.math
Subject: 21 primes in arithmetic progression (LaTeX announcement)
Keywords: prime number
Message-ID: <pap.664587061@neptune>
Date: 22 Jan 91 23:31:01 GMT
Sender: news@anucsd.anu.oz.au (USENET News software)
Organization: ANU Department of Computer Science
Lines: 54
 
\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.75in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\addtolength{\oddsidemargin}{-.75in}
\addtolength{\textwidth}{1.5in}
\addtolength{\textheight}{3.25in}
\title{There is an arithmetic progression of 21 primes}
\author{Andrew Moran \\ Department of Computer Science \\ University of Queensland
	\\ Queensland, Australia 4072
	\\ {[}e-mail: angst@batserver.cs.uq.oz.au]
	\and
	Paul Pritchard \\ School of Computing and Information Technology
	\\ Griffith University \\ Nathan, Queensland, Australia 4111
	\\ {[}e-mail: pap@gucis.sct.gu.edu.au]}
\date{\empty}
 
\begin{document}
\maketitle
\thispagestyle{empty}
 
The following AP of 21 primes was discovered on 30 November 1990, by programs
running in the background on a network of Sun 3 workstations
in the Department of Computer Science, University of Queensland.\footnote{
See: Andrew Moran and Paul Pritchard, The design of a background job
on a local area network, {\em Procs. 14th Australian Computer Science Conference},
1991, to appear.}
 
{\large
\[\begin{array}{r}
142072321123 \\
1561835345803 \\
2981598370483 \\
4401361395163 \\
5821124419843 \\
7240887444523 \\
8660650469203 \\
10080413493883 \\
11500176518563 \\
12919939543243 \\
14339702567923 \\
15759465592603 \\
17179228617283 \\
18598991641963 \\
20018754666643 \\
21438517691323 \\
22858280716003 \\
24278043740683 \\
25697806765363 \\
27117569790043 \\
28537332814723
\end{array}\]}
 
\end{document}
4.2GUESS::DERAMODan D'EramoWed Jan 30 1991 16:0720
        Consider each of the p numbers a, a + d, a + 2d, ..., a + (p-1)d
        for some prime p.
        
        If p does not divide d, then the residues mod p of these
        numbers are all different.  Thus one of the residues mod p
        is zero, and that number is divisible by p, and so isn't
        prime (unless it is p itself).
        
        So to find an arithmetic progression of 21 consecutive
        primes, which includes subprogressions of 2, 3, 5, 7,
        ..., 19 consecutive primes, it must be the case that d is
        divisible by each of 2, 3, 5, 7, ..., 19 (or that 2, 3,
        ... etc. is a member of the progression).
        
        In this case d = 1419763024680 = 146372 * (2 * 3 * 5 * 7
        * 11 * 13 * 17 * 19) [where 146372 = 4 * 23 * 37 * 43]. 
        Notice the 23.  Perhaps they were hoping to find an even
        longer progression.
        
        Dan
4.3CHOVAX::YOUNGDigital WeatherMan.Thu Jan 31 1991 00:336
    Re .2:
    
    Extending the same logic we can also conclude that 'a' must NOT be
    divisible by any of 2,3,5,7,...19.  Right?
    
    --  Barry
4.4GUESS::DERAMODan D'EramoThu Jan 31 1991 04:1220
        re .3,
        
        Sounds good.
        
        Thw first p+1 elements of the progression are a, a+d,
        ..., a + pd.  [a,d,p positive integers, p prime]
        
        p | a, p | d => no primes if p ~= a, one prime if p = a
        
        p | a, p ~| d => first term not prime unless p = a, in
        any case p+1st term a+pd is not prime
        
        p ~| a, p ~| d => one of the first p terms is divisible
        by p
        
        Therefore first p+1 terms prime => p ~| a, p | d.
        First p terms prime => p ~| a, p | d ; or p = a, p ~| d.
        
        Dan
        
4.511410337850553 + (0..21)4609098694200CADSYS::COOPERTopher CooperMon Mar 22 1993 18:0962
Newsgroups: sci.math
From: pap@kurango.cit.gu.edu.au (Paul Pritchard)
Subject: 22 primes in AP (LaTeX poster)
Message-ID: <C42Cyz.J6E@kurango.cit.gu.edu.au>
Organization: Griffith University.
Date: Thu, 18 Mar 1993 02:44:58 GMT
Lines: 54

\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.75in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\addtolength{\oddsidemargin}{-.75in}
\addtolength{\textwidth}{1.5in}
\addtolength{\textheight}{3.25in}
\title{There is an arithmetic progression of 22 primes}
\author{Paul Pritchard and Anthony Thyssen
        \\  School of Computing and Information Technology
	\\ Griffith University \\ Queensland, Australia 4111
	\\ e-mail: \{pap,anthony\}@cit.gu.edu.au}
\date{18 March 1993}

\begin{document}
\maketitle
\thispagestyle{empty}

The first known AP of 22 primes below was discovered on 17 March 1993,
by the Sun SPARCstation ``pil'' in the Parallel Processing
Laboratory of the University of Bergen, Norway. It is one of over 60
computers participating in a distributed background search
co-ordinated at the School of Computing and Information Technology
at Griffith University, Australia, which also involves computers
at the Department of Computing Sciences at the Chalmers University
of Technology in Sweden.

{\large
\[\begin{array}{r}
11410337850553 \\
16019436544753 \\
20628535238953 \\
25237633933153 \\
29846732627353 \\
34455831321553 \\
39064930015753 \\
43674028709953 \\
48283127404153 \\
52892226098353 \\
57501324792553 \\
62110423486753 \\
66719522180953 \\
71328620875153 \\
75937719569353 \\
80546818263553 \\
85155916957753 \\
89765015651953 \\
94374114346153 \\
98983213040353 \\
103592311734553 \\
108201410428753
\end{array}\]}

\end{document}
4.6certificates of primality for .-1CSC32::D_DERAMODan D'Eramo, Customer Support CenterTue Mar 23 1993 13:34149
Article 41992 of sci.math:
Newsgroups: sci.math
Path: nntpd2.cxo.dec.com!nntpd.lkg.dec.com!news.crl.dec.com!deccrl!decwrl!decwrl!concert!gatech!howland.reston.ans.net!zaphod.mps.ohio-state.edu!uwm.edu!caen!batcomputer!munnari.oz.au!bunyip.cc.uq.oz.au!griffin!kurango!pap
From: pap@kurango.cit.gu.edu.au (Paul Pritchard)
Subject: 22 primes in arithmetic progression
Message-ID: <C42Cv7.J3G@kurango.cit.gu.edu.au>
Organization: Griffith University.
Date: Wed, 17 Mar 93 19:42:42 MST
Lines: 139

The first known arithmetic progression of 22 primes
has just been discovered:

  11410337850553 + 4609098694200 i, 0 <= i < 22.

It was discovered on 17 March 1993,
by the Sun SPARCstation ``pil'' in the Parallel Processing
Laboratory of the University of Bergen, Norway. It is one of
over 60 computers participating in a distributed background
search co-ordinated at the School of Computing and Information
Technology at Griffith University, Australia, which also
involves computers at the Department of Computing Sciences at
the Chalmers University of Technology in Sweden.

For a 1-page poster of this discovery, process the
accompanying posting with LaTeX.

The common difference 4609098694200 has the prime factorization

  2.2.2.3.5.5.7.11.13.17.19.23.1033

Richard Brent (RPB@PHYS4.anu.edu.au) has kindly verified
the primality of each term of the AP. He writes:

A "certificate" for each prime follows.
The certificate for prime p is a factorisation of p-1 and a
primitive root (in square brackets) which can be used to prove
p prime. If the factors are too large to be proved prime by
division up to square root, then the algorithm is applied
recursively.

e.g. the first number is p0 = 11410337850553,
     p0 has primitive root 5 and p0-1 has a factor
	p1 = 52825638197,
	p1 has primitive root 2 and p1-1 has a factor
	   p2 = 9177491,
	   p2 has primitive root 2.
Term 0:
11410337850553 = 1 + 2.2.2.3.3.3.
  (52825638197 = 1 + 2.2.1439.
    (9177491 = 1 + 2.5.7.43.3049 [2]) [2]) [5]

Term 1:
16019436544753 = 1 + 2.2.2.2.3.233.499.
  (2870447 = 1 + 2.23.62401 [5]) [7]

Term 2:
20628535238953 = 1 + 2.2.2.3.67.83.151.317.3229 [5]

Term 3:
25237633933153 = 1 + 2.2.2.2.2.3.3.5717.
  (15328087 = 1 + 2.3.139.18379 [5]) [5]

Term 4:
29846732627353 = 1 + 2.2.2.3.41.13451.
  (2255003 = 1 + 2.31.37.983 [2]) [7]

Term 5:
34455831321553 = 1 + 2.2.2.2.3.22381.
  (32073179 = 1 + 2.19.23.36697 [2]) [5]

Term 6:
39064930015753 = 1 + 2.2.2.3.3.71.659.
  (11596069 = 1 + 2.2.3.3.3.11.43.227 [2]) [5]

Term 7:
43674028709953 = 1 + 2.2.2.2.2.2.3.293.8291.93637 [5]

Term 8:
48283127404153 = 1 + 2.2.2.3.1367.80363.18313 [7]

Term 9:
52892226098353 = 1 + 2.2.2.2.3.3.3.
  (122435708561 = 1 + 2.2.2.2.5.11.11.11.521.2207 [6]) [5]

Term 10:
57501324792553 = 1 + 2.2.2.3.1723.
  (1390533101 = 1 + 2.2.5.5.11.347.3643 [2]) [10]

Term 11:
62110423486753 = 1 + 2.2.2.2.2.3.
  (646983577987 = 1 + 2.3.23.181.
    (25902137 = 1 + 2.2.2.13.
      (249059 = 1 + 2.
        (124529 = 1 + 2.2.2.2.43.181 [3]) [2]) [3]) [2]) [5]

Term 12:
66719522180953 = 1 + 2.2.2.3.3.
  (926660030291 = 1 + 2.5.487.
    (190279267 = 1 + 2.3.17.29.64327 [3]) [2]) [7]

Term 13:
71328620875153 = 1 + 2.2.2.2.3.
  (1486012934899 = 1 + 2.3.3.37.113.
    (19745581 = 1 + 2.2.3.5.191.1723 [6]) [2]) [5]

Term 14:
75937719569353 = 1 + 2.2.2.3.241.30497.
  (430499 = 1 + 2.
    (215249 = 1 + 2.2.2.2.11.1223 [3]) [2]) [10]

Term 15:
80546818263553 = 1 + 2.2.2.2.2.2.2.2.2.3.3.13291.
  (1315159 = 1 + 2.3.13.13.1297 [3]) [5]

Term 16:
85155916957753 = 1 + 2.2.2.3.88547.
  (40070959 = 1 + 2.3.67.99679 [15]) [5]
Term 17:
89765015651953 = 1 + 2.2.2.2.3.31.12473.
  (4836523 = 1 + 2.3.
    (806087 = 1 + 2.
      (403043 = 1 + 2.29.6949 [2]) [5]) [2]) [5]

Term 18:
94374114346153 = 1 + 2.2.2.3.3.3.3.6373.
  (22852513 = 1 + 2.2.2.2.2.3.3.79349 [5]) [5]

Term 19:
98983213040353 = 1 + 2.2.2.2.2.3.
  (1031075135837 = 1 + 2.2.23.103.
    (108809111 = 1 + 2.5.1693.6427 [11]) [2]) [7]

Term 20:
103592311734553 = 1 + 2.2.2.3.
  (4316346322273 = 1 + 2.2.2.2.2.3.3.577.1103.23549 [5]) [5]

Term 21:
108201410428753 = 1 + 2.2.2.2.3.3.6299.8963.13309 [5]

Paul Pritchard and Anthony Thyssen                   _--_|\
School of Computing & Information Technology        /      GU
Griffith University, Queensland, AUSTRALIA 4111     \_.--._/
phone: +61 7 875 5010; fax: + 61 7 875 5051               v
-- 
Paul Pritchard (pap@cit.gu.edu.au)                   _--_|\
Head, School of Computing & Information Technology  /      GU
Griffith University, Queensland, AUSTRALIA 4111     \_.--._/
phone: +61 7 875 5010; fax: + 61 7 875 5051               v
4.7AMCFAC::RABAHYdtn 471-5411Wed Mar 24 1993 17:153
    RE: 4.6
    
    What is a primative root?
4.8some related stuffSTAR::ABBASIi am therfore i thinkWed Mar 24 1993 17:4560
.-1
    that also confuses me too, (number theory confuses me any way), but i 
    asked MAPLE on some defintions, and this might help..
   
FUNCTION: numtheory[pprimroot] - compute a pseudo primitive root
   
CALLING SEQUENCE:
   pprimroot(g, n)
   
PARAMETERS:
   g - an integer
   n - an integer greater than 2
   
SYNOPSIS:   
- The function pprimroot(g, n) computes the next primitive root larger than g
  or, if n does not have primitive roots, computes a number which is not a root
  of order of any of the factors of phi(n).
   
- I.e. (in all cases), find an integer y, such that there is no x for which
  x^r = y (mod n) when r is a divisor of phi(n) greater than 1 and
  igcd(y, n) = 1.
   
EXAMPLES:   
> with(numtheory):
> pprimroot(1,41);
                                       6
> pprimroot(2,8);
                                       3
   
SEE ALSO:  numtheory[primroot]

?numtheory[primroot]
   
FUNCTION: numtheory[primroot] - compute a primitive root
   
CALLING SEQUENCE:
   primroot(g, n)
   
PARAMETERS:
   g - an integer
   n - an integer greater than 2
   
SYNOPSIS:   
- The function primroot will compute the first primitive root of n, that is
  greater than g, if possible, otherwise it returns FAIL.  The integers that
  are relatively prime to n form a group of order phi(p) under multiplication
  (mod n). If this group is cyclic then a generator of the group is called a
  primitive root of n.
   
EXAMPLES:   
> with(numtheory):
> primroot(1,41);
                                       6
   
> primroot(2,8);
                                      FAIL
   
SEE ALSO:  numtheory[pprimroot]

    
4.93D::ROTHGeometry is the real life!Wed Mar 24 1993 17:4614
>                <<< Note 4.7 by AMCFAC::RABAHY "dtn 471-5411" >>>
>    RE: 4.6
>    
>   What is a primative root?

    That's an element that generates the multiplicative
    group of the integers mod p, p a prime.

    For example, 3 is a primitive root mod 7.

    More generally, an element of an extension of a finite field
    is primitive if its powers generate the multiplicative group.

    - Jim
4.10what is a cyclic group?AMCFAC::RABAHYdtn 471-5411Wed Mar 24 1993 19:3813
    RE: .8, .9
    
    I know what relatively prime is.  For example, 6 and 35 are relatively
    prime even though neither one is prime itself.  They share no prime
    factor.  I understand modular arithmetic.  A clock is the typical
    example - so, 13 = 1 mod 12.  I understand what closure is.  The whole
    numbers are closed under addition.  The sum of any two whole numbers is
    a whole number.
    
    I think I may have once known what a group is.  As I recall it is a set
    of numbers and functions that exhibited closure.  Certainly it is a
    concept from algebraic theory.  Perhaps my understanding on this point
    is too weak - I couldn't follow the MAPLE explaination.
4.11RUSURE::EDPAlways mount a scratch monkey.Thu Mar 25 1993 12:1516
    Re .10:
    
    A group is an ordered pair (S,*) consisting of a set S and a closed,
    associative binary operation * on S which has an identity element (an
    element e such that for each a in S, a*e=a) and such that each element
    has an inverse (for each a in S, there is a b in S such that a*b=e).
    
    A cyclic group is one generated by some single element of the set, such
    as a.  That is, for each element b in S, there exists an integer n such
    that a^n=b, where
    
    		a^0 = e, and
    		a^(n+1) = a*a^n.
    
    
    				-- edp
4.12HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Thu Mar 25 1993 14:1816
   
    A cyclic group is one generated by some single element of the set, such
    as a.  That is, for each element b in S, there exists an integer n such
    that a^n=b, where
    
    		a^0 = e, and
    		a^(n+1) = a*a^n.
    
    
    				-- edp

So, does this relate to the statement that "3 is a primitive root of 7" ?
Is it that 3^0, 3^1, 3^2... taken modulo 7 produce *every* value modulo 7, i.e.
we'll "hit" all of 0,1,2,3,4,5,6 (in some order) ?

/Eric
4.13Except 0, which ain't in the multiplicative groupVMSDEV::HALLYBFish have no concept of fire.Thu Mar 25 1993 14:403
    Eric (O), you have lurched uncontrollably into the truth!
    
      John (with apologies to John McLaughlin and Eric Osman)
4.14thanks EricAMCFAC::RABAHYdtn 471-5411Thu Mar 25 1993 15:0340
    	3^0 =    1 = 1 mod 7
    	3^1 =    3 = 3 mod 7
    	3^2 =    9 = 2 mod 7
    	3^3 =   27 = 6 mod 7
    	3^4 =   81 = 4 mod 7
    	3^5 =  243 = 5 mod 7
    
    	3^6 =  729 = 1 mod 7
    	3^7 = 2187 = 3 mod 7
    		...
    
    RE: .12
    
    Naturally, 3^n is never divisible by 7 and so will never equal 0 mod 7.
    The next best thing is to get 7-1 unique results before repeating.
    
    So, let's see, for example, what is the primative root of 11?  We need
    to find a number such that we get 11-1 unique results before repeating. 
    Ah, further the smallest number with this property is the primative
    root as opposed to just being a root.  Brute force reveals;
    
    	2^0  =    1 =  1 mod 11
    	2^1  =    2 =  2 mod 11
    	2^3  =    8 =  8 mod 11
    	2^4  =   16 =  5 mod 11
    	2^5  =   32 = 10 mod 11
    	2^6  =   64 =  9 mod 11
    	2^7  =  128 =  7 mod 11
    	2^8  =  256 =  3 mod 11
    	2^9  =  512 =  6 mod 11
    
    	2^10 = 1024 =  1 mod 11
    	2^11 = 2048 =  2 mod 11
    		...
    
    bit of luck there (pardon the pun).  So what is the primative root of
    say 101?
    
    Now, I may be ready for the leap to how this relates to the primality
    of a number.
4.15AMCFAC::RABAHYdtn 471-5411Thu Mar 25 1993 15:138
    RE: .14
    
    Oops, I see 3 is a primitive root of 7.  No name has been given for the
    smallest primitive root.  The MAPLE function gives the next higher
    number above the first parameter which is a primitive root of the
    second parameter.
    
    Step by step I will understand this stuff.  Please excuse my density.
4.16HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Fri Mar 26 1993 20:11157

	Can two numbers be relatively prime, such that the smaller is *not*
	a "primitive root" of the larger ?

	For example, picking a random example:

		4 is relatively prime with 45

	Is 4 a primitive root of 45 ?

	(Actually, no one confirmed my question yet.  Did I give the right
	definition of "primitive root of n", namely a number p whose integer
	powers taken modulo n produce every possible integer 0 through n-1 ?)

	Anway, assuming that's the correct definition, let's look at the
	powers of 4 modulo 45:

		4,16,19,31,34,1,4...

	Gee, we didn't get very far !  So, my the answer is

		No, numbers can easily be relatively prime without the
		smaller being a primitive root.

	Then, what is needed for a number to be a primitive root ?  Maybe
	the smaller number has to be prime ?  For example:

		7 is relatively prime with 45

	Is 7, a primitive root of 45 ?  Let's try:

		4,28,16,22,19,43,31,37,34,13,1,7,4,...

	Nope!  So, what's a primitive root of 45 ?  I wrote a .COM file to
	calculate it:

$ best = 0
$ root = 1
$ high = 49
$ write sys$output "Looking for primitive roots of ", high
$ outer_lup:
$ n = root
$ i = 0
$ result = ","
$ lup:
$ n = n*root
$ if n .ge. high then n = n - n/high*high
$ if f$loc(","+f$str(n)+",",result) .ne. f$len(result)
$ then
$	if i .gt. best
$	then
$		write sys$output f$fao("!ZL hits !ZL power!%S of !ZL:", -
		    root,i,high)
$		write sys$output root,result+"*" - (","+f$str(root)+",*")
$		best = i
$	endif
$	root = root + 1
$	if root .lt. high then goto outer_lup
$	exit
$ endif
$ result = result + f$string(n) + ","
$ i = i + 1
$ goto lup

	Here's what it gives:

Looking for primitive roots of 45
1 hits 1 power of 45:
1
2 hits 12 powers of 45:
2,4,8,16,32,19,38,31,17,34,23,1



	So, there *are* no primitive roots of 45.  Let's try 49:

Looking for primitive roots of 49
1 hits 1 power of 49:
1
2 hits 21 powers of 49:
2,4,8,16,32,15,30,11,22,44,39,29,9,18,36,23,46,43,37,25,1
3 hits 42 powers of 49:
3,9,27,32,47,43,31,44,34,4,12,36,10,30,41,25,26,29,38,16,48,46,40,22,17,2,6,18,5
,15,45,37,13,39,19,8,24,23,20,11,33,1

	3 was pretty good, but it still didn't hit all possible powers.  (Is
	there a bug in my program ?)

	Let's try 47:

Looking for primitive roots of 47
1 hits 1 power of 47:
1
2 hits 23 powers of 47:
2,4,8,16,32,17,34,21,42,37,27,7,14,28,9,18,36,25,3,6,12,24,1
5 hits 46 powers of 47:
5,25,31,14,23,21,11,8,40,12,13,18,43,27,41,17,38,2,10,3,15,28,46,42,22,16,33,24,
26,36,39,7,35,34,29,4,20,6,30,9,45,37,44,32,19,1

	So, 5 is a primitive root of 47.

	Perhaps only *prime* numbers have primitive roots ?  Do *all* prime
	numbers have them ?

	Let's try random ones.  How about 53:

1 hits 1 power of 53:
1
2 hits 52 powers of 53:
2,4,8,16,32,11,22,44,35,17,34,15,30,7,14,28,3,6,12,24,48,43,33,13,26,52,51,49,45
,37,21,42,31,9,18,36,19,38,23,46,39,25,50,47,41,29,5,10,20,40,27,1

	So, 2 is a primitive root of 53.

	It's interesting to note that neither 2 nor 3 are primitive roots of
	47.

	Why not ?  Rather than brute force try all the powers, is there a
	faster way to tell what the smallest primitive root of a number will
	be, or that a number is not a primitive root of something ?

	For example, what effort is needed to *know* that 2 is not a primitive
	root of 47, and that it will only hit *half* the powers ?

Let's try a few more.  How about 17:

Looking for primitive roots of 17
1 hits 1 power of 17:
1
2 hits 8 powers of 17:
2,4,8,16,15,13,9,1
3 hits 16 powers of 17:
3,9,10,13,5,15,11,16,14,8,7,4,12,2,6,1

	So, 3 is a p.r. of 17.

	Which primes *won't* have 2 or 3 as a primitive root ?  For example, 5
	seems to be smallest primitive root of 47.

	How about 23 :

Looking for primitive roots of 23
1 hits 1 power of 23:
1
2 hits 11 powers of 23:
2,4,8,16,9,18,13,3,6,12,1
5 hits 22 powers of 23:
5,2,10,4,20,8,17,16,11,9,22,18,21,13,19,3,15,6,7,12,14,1

	Again, 5 pops up.  How can we find numbers with large minimal primitive
	roots ?  Perhaps these numbers can be considered in some respect "more
	prime" than others ?

	What  numbers have larger minimal p.r.'s than 5 ?

/Eric
4.17re -.1HERON::BUCHANANThe was not found.Sun Mar 28 1993 11:3133
4.18re .6HERON::BUCHANANThe was not found.Sun Mar 28 1993 11:4918
>A "certificate" for each prime follows.
>The certificate for prime p is a factorisation of p-1 and a
>primitive root (in square brackets) which can be used to prove
>p prime. If the factors are too large to be proved prime by
>division up to square root, then the algorithm is applied
>recursively.

>Term 0:
>11410337850553 = 1 + 2.2.2.3.3.3.
>  (52825638197 = 1 + 2.2.1439.
>    (9177491 = 1 + 2.5.7.43.3049 [2]) [2]) [5]

	How does this figure?   You've got n, and you've got r such that
r^(n-1) == 1 mod n.   But you've also got all the prime factors p_i of n-1, and
by trying them in turn you can show that r^((n-1)/p_i) <> 1 mod n.   ie: the
order of r *is* n-1.   The only way this can happen is if n is prime.

Andrew
4.19AMCFAC::RABAHYdtn 471-5411Mon Mar 29 1993 17:577
    RE: .16

	(Actually, no one confirmed my question yet.  Did I give the right
	definition of "primitive root of n", namely a number p whose integer
	powers taken modulo n produce every possible integer 0 through n-1 ?)

    Please see .13 for confirmation.
4.20HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Tue May 04 1993 19:0455
4.213D::ROTHGeometry is the real life!Wed May 05 1993 21:1040
 Re .20 - this recent note from sci.math may be of interest
 (the facts Bob Silverman cites are in most books on number theory)

 I'd forgotten about the twice-primes part about primitive roots.

 - Jim

Article: 42320
Newsgroups: sci.math
From: bs@gauss.mitre.org (Robert D. Silverman)
Subject: Re: Primitive Roots of Numbers
Keywords: Primitive Roots, Roots
Sender: news@linus.mitre.org (News Service)
Nntp-Posting-Host: gauss.mitre.org
Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
Date: Wed, 5 May 1993 15:48:02 GMT
Lines: 25
 
In article <1851@pacs.pha.pa.us> gre@pacs.pha.pa.us ( Jim Greene) writes:
>What are Primitive Roots of Numbers?

Not numbers in general. Only primes, twice primes, and powers of primes
have primitive roots. A number a is a primitive root of p iff a^h != 1
mod p for any integer h smaller than p-1.
 
Primitive roots are generators of the group Z/pZ*

...
 
>How can you find the Primitive Roots of a Number?
 
Basically by direct search. One tries integers 2,3,5,6... at random
until one is found. Since there are phi(p-1) primitive roots in
Z/pZ* you can find one quickly.
 
--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"
4.22HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Thu May 06 1993 15:3221
>>What are Primitive Roots of Numbers?
>
>Not numbers in general. Only primes, twice primes, and powers of primes
>have primitive roots. A number a is a primitive root of p iff a^h != 1
>mod p for any integer h smaller than p-1.


I'm having trouble with this definition.  Consider the number 46, which is
twice a prime.  Assuming that 46 *has* a primitive root, what would it be ?

The best number I can come up with is 5, but the powers of 5 mod 46 yield:

	5,25,33,27,43,31,17,39,11,9,45,41,21,13,19,3,15,29,7,35,37,1

Note that 1 appears at h=22, which is much smaller than 46-1.



/Eric


4.23attempt to clarifyHERON::BUCHANANThe was not found.Fri May 07 1993 09:5823
Hi Eric,

>I'm having trouble with this definition.  Consider the number 46, which is
>twice a prime.  Assuming that 46 *has* a primitive root, what would it be ?
>
>The best number I can come up with is 5, but the powers of 5 mod 46 yield:
>
>	5,25,33,27,43,31,17,39,11,9,45,41,21,13,19,3,15,29,7,35,37,1
>
>Note that 1 appears at h=22, which is much smaller than 46-1.

	Ah, I think I see your difficulty.   We are *only* interested in the
numbers which are coprime to n.   For instance, with n=46, we don't care
about the even numbers, or about 23.   That leaves us with 46/2-1=22 numbers
coprime to 46.   This set forms a group.

	Our question is: is this group of 22 elements cyclic?   Ie, does it
have a generator which generates the entire group by itself.   Another name
for such a generator is primitive root, or primitive element.   Since, as
you show, 5 generates all 22 fellows coprime to 46, 5 is indeed a primitive
root of 46.

Andrew.
4.24behavior of b,b^2,b^3,... modulo nCSC32::D_DERAMODan D'Eramo, Customer Support CenterWed May 12 1993 17:4480
        Suppose n, b, and k are integers, n > 1, and k > 0.

        Let q(k) and r(k) represent the quotient and remainder when
        you divide b^k by n,

        	b^k = n q(k) + r(k)	0 <= r(k) < n

        So what Eric was looking at with his .COM file program was the
        sequence <r(k) : k = 1,2,3,...> generated by different choices
        for n and the base b.

        If a number m divides two of b^k, n q(k), and r(k) then it
        must also divide the third.  So we can immediately see

        ***** If a prime p divides both n and b, then p also     *****
        ***** divides every r(k).                                *****
        *****                                                    *****
        ***** Still assuming the prime p divides both n and b,   *****
        ***** if p^j is the largest power of p which divides n,  *****
        ***** and p^i is the largest power of p which divides b, *****
        ***** then r(k) is divisible by at least the power       *****
        ***** p^(min(j,ki)) of p.                                *****

        Now suppose p is any prime which divides both n and r(k). 
        Then p divides both n q(k) and r(k) and so p divides their
        sum, which is b^k.  Now primes have the wonderful property
        that if a prime p divides the product st then p divides either
        s or t (or both).  So by induction you can prove that if p
        divides b^k then p divides b.  So we also have

        ***** If a prime p divides both n and some element r(k)  *****
        ***** of the sequence, then p divides b (and therefore   *****
        ***** by the above p divides every r(k).                 *****

        You can use this to guide what you search for:

        Relatively prime or not relatively prime to n:

        	If b is relatively prime to n, then all of the r(k)
        	will be relatively prime to n as well.  If b is not
        	relatively prime to n and p is a prime which divides
        	both n and b, then p divides all of the r(k) as well.

        	(As Andrew said in .17, if n is 2, 4, a power of an
        	odd prime, or twice a power of an odd prime, then
        	there is a "primitive root" b relatively prime to n
        	such that the r(k) cover all of the positive integers
        	less than n and relatively prime to n.)

        Does 0 occur among the r(k)?

        	If n = p1^e1 * p2^e2 * ... * pj^ej is the
        	factorization of n with p1,p2,...,pj distinct primes,
        	then if 0 occurs among the r(k), then b must be
        	divisible by each of p1,p2,...,pj.  Conversely, if
        	b is divisible by each of p1,p2,...,pj then 0 will
        	occur among the r(k).

        	So if n is prime, or a product of distinct primes,
        	then either every r(k) is zero or every r(k) is non-zero.

        	For n = 46, b must be 0 modulo 46 in order for any
        	r(k) to be 0, and then all r(k) are 0.  For n = 54,
        	b must be a multiple of 6 for some r(k) to be 0, and
        	then all r(k) for k >= 3 will be 0.

        n = 46:

        	If b = 0 modulo 46 then the r(k) sequence is 0,0,0,...

        	If b = 23 modulo 46 then the r(k) sequence is 23,23,23,...

        	If b = 5 modulo 46 then the r(k) cycle through all 22
        	positive integers less than 46 and relatively prime to
        	46.

        	What about the 22 remaining numbers, i.e., the nonnegative,
        	nonzero, even integers less than 46?  Hint: try b = 10.

        Dan