NAME

Math::NumSeq::LeastPrimitiveRoot -- smallest primitive root

SYNOPSIS

use Math::NumSeq::LeastPrimitiveRoot;
my $seq = Math::NumSeq::LeastPrimitiveRoot->new;
my ($i, $value) = $seq->next;

DESCRIPTION

In progress ...

This is the least primitive root modulo i,

3, 3, 5, 4, 4, 3, 5, 5, 4, 3, 6, 6, 8, 8, 7, 7, 9, 8, 8, ...
starting i=1

A primitive root is a base b for which

b^totient(i) == 1 modulo i
and all smaller exponents b^e != 1 modulo i

The powers of a base b taken modulo i are a multiplicative group

b^0, b^1, b^2, b^3, etc  modulo i

Eventually a power b^k == 1 modulo i is reached. The k where that happens is called the multiplicative order. The multiplicative order can be at most totient(i). For some bases b it's smaller. A base b for which the multiplicative order is the full totient(i) is a primitive root. The sequence here gives the first base b with that maximum multiplicative order.

For i prime totient(i)=i-1 and the set of powers of a primitive root gives all the integers 1 to i-1. For i composite totient(i) is smaller and the powers aren't consecutive integers.

FUNCTIONS

See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.

$seq = Math::NumSeq::LeastPrimitiveRoot->new ()

Create and return a new sequence object.

Random Access

$value = $seq->ith($i)

Return the first primitive root to modulus $i.

$i = $seq->i_start ()

Return 1, the first term in the sequence being at i=1.

SEE ALSO

Math::NumSeq

HOME PAGE

http://user42.tuxfamily.org/math-numseq/index.html

LICENSE

Copyright 2012, 2013, 2014, 2016, 2019, 2020 Kevin Ryde

Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.