Conference rusure::math

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: [email protected] (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: [email protected] (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: [email protected]; 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: [email protected] (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: [email protected] (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: [email protected]]
	\and
	Paul Pritchard \\ School of Computing and Information Technology
	\\ Griffith University \\ Nathan, Queensland, Australia 4111
	\\ {[}e-mail: [email protected]]}
\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}

        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

    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

        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
        

Newsgroups: sci.math
From: [email protected] (Paul Pritchard)
Subject: 22 primes in AP (LaTeX poster)
Message-ID: <[email protected]>
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}

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: [email protected] (Paul Pritchard)
Subject: 22 primes in arithmetic progression
Message-ID: <[email protected]>
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 ([email protected]) 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 ([email protected])                   _--_|\
Head, School of Computing & Information Technology  /      GU
Griffith University, Queensland, AUSTRALIA 4111     \_.--._/
phone: +61 7 875 5010; fax: + 61 7 875 5051               v

    RE: 4.6
    
    What is a primative root?

.-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]

    

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

    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.

    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

   
    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

    Eric (O), you have lurched uncontrollably into the truth!
    
      John (with apologies to John McLaughlin and Eric Osman)

    	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.

    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.

	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

Eric,

	Your definition of primitive roots looks OK.   Here's some theory.

	The integers mod n which are coprime to n are called the residue
classes mod n.   Under multiplication, they form an abelian group, call it
G(n).   If m & m' are coprime, then G(mm') == G(m) x G(m').   If p is 
an odd prime, then G(p^a) == C((p-1)(p^(a-1))), where C(n) denotes the cyclic 
group of order n.   G(2^a) == C(2) x C(2^(a-2)), for a >= 2.   G(2) == I.

	Because we'll need it later, let |G(n)| be denoted �(n).

	Now, a primitive root x of n will exist exactly if G(n) is cyclic,
because then x is a generator of the group.   G(n) is cyclic iff 
		(i) n is an odd prime power, 
		(ii) twice an odd prime power,
	     or (iii) 4.

	How many generators will G(n) have, assuming that n takes on of the 
forms above?   We can write it �(�(n)).   If n = p^a or 2p^a, then this becomes:
		�(p-1)*(p-1)*p^(a-2) if a>=2,
		�(p-1)		     if a=1.
	G(4) has exactly 1 generator, 3.

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

	So, G(45) is not cyclic, and has no primitive roots.   The group is
G(5) x G(9) = C(4) x C(6).   The largest order any element can have in this
group is 12, not 24.   The element 4 has order 6.

	However G(46) *is* cyclic, and will have �(22) = 10 generators.

Andrew

>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

    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.

>	However G(46) *is* cyclic, and will have �(22) = 10 generators.
>
>Andrew
>


This statement confused me for awile.  At first I thought it meant that
you were saying that 46 has at least one primitive root.  My program can't
find any though.

On closer reading, I realize you are saying that G(46) refers to a group whose
elements are all the numbers coprime to 46, namely:

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

5 is a generator of this group, since the powers of 5 taken modulo 46
produces:

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


But by my definition, 5 is not a primitive root of 46, 5 is a primitive root
of 23.  So, it sounds like my definition of primitive root is different
from yours.  Yours seems to be embedded in this:


>	Now, a primitive root x of n will exist exactly if G(n) is cyclic,
>because then x is a generator of the group.   G(n) is cyclic iff 
>		(i) n is an odd prime power, 
>		(ii) twice an odd prime power,
>	     or (iii) 4.

By that definition, you would say

	"the primitive root 5 of 46 exists since G(46) is cyclic, with 5
	being a generator of the group"

But, my definition of primitive group was:

	A primitive root x of n exists if the powers of x taken modulo n
	produce all the numbers 1,2,3,4...n-1

So, for example, I say 5 is a primitive root of 23 because the powers of 5
taken modulo 23 cover all the numbers 1,2,3,4...22:

	5,2,10,4,20,8,17,16,11,9,22,18,21,13,19,3,15,6,7,12,14,1

I guess I'm still confused about what the real definition is, especially
since you originally said mine "looks o.k.".

Oh well, it's back to the drawing board for me a bit I guess...

/Eric

 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: [email protected] (Robert D. Silverman)
Subject: Re: Primitive Roots of Numbers
Keywords: Primitive Roots, Roots
Sender: [email protected] (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 <[email protected]> [email protected] ( 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"

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

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.

        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