%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  numtheor.msk                GAP documentation            Martin Schoenert
%A                                                           Alexander Hulpke
%%
%A  @(#)$Id: numtheor.msk,v 1.17.2.2 2005/05/10 08:55:31 gap Exp $
%%
%Y  (C) 1998 School Math and Comp. Sci., University of St.  Andrews, Scotland
%Y  Copyright (C) 2002 The GAP Group
%%
\Chapter{Number Theory}

\index{prime residue group}

\FileHeader{numtheor}[1]

\Declaration{InfoNumtheor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Prime Residues}

\Declaration{PrimeResidues}!{function}
\index{prime residue group}

\beginexample
gap> PrimeResidues( 0 );  PrimeResidues( 1 );  PrimeResidues( 20 );
[  ]
[ 0 ]
[ 1, 3, 7, 9, 11, 13, 17, 19 ]
\endexample

\Declaration{Phi}
\index{order!of the prime residue group}
\index{prime residue group!order}
\atindex{Euler's totient function}{@Euler's totient function}

\beginexample
gap> Phi( 12 );
4
gap> Phi( 2^13-1 );  # this proves that 2^(13)-1 is a prime
8190
gap> Phi( 2^15-1 );
27000
\endexample

\Declaration{Lambda}
\atindex{Carmichael's lambda function}{@Carmichael's lambda function}
\index{prime residue group!exponent}
\index{exponent!of the prime residue group}

\beginexample
gap> Lambda( 10 );
4
gap> Lambda( 30 );
4
gap> Lambda( 561 );  # 561 is the smallest Carmichael number
80
\endexample

\Declaration{GeneratorsPrimeResidues}

\beginexample
gap> GeneratorsPrimeResidues( 1 );
rec( primes := [  ], exponents := [  ], generators := [  ] )
gap> GeneratorsPrimeResidues( 4*3 );
rec( primes := [ 2, 3 ], exponents := [ 2, 1 ], generators := [ 7, 5 ] )
gap> GeneratorsPrimeResidues( 8*9*5 );
rec( primes := [ 2, 3, 5 ], exponents := [ 3, 2, 1 ], 
  generators := [ [ 271, 181 ], 281, 217 ] )
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Primitive Roots and Discrete Logarithms}

\Declaration{OrderMod}
\index{multiplicative order of an integer}

\beginexample
gap> OrderMod( 2, 7 );
3
gap> OrderMod( 3, 7 );  # 3 is a primitive root modulo 7
6
\endexample

\Declaration{LogMod}
\index{logarithm!discrete}

\beginexample
gap> l:= LogMod( 2, 5, 7 );  5^l mod 7 = 2;
4
true
gap> LogMod( 1, 3, 3 );  LogMod( 2, 3, 3 );
0
fail
\endexample

\Declaration{PrimitiveRootMod}
\index{primitive root modulo an integer}
\index{prime residue group!generator}
\index{generator!of the prime residue group}

\beginexample
gap> PrimitiveRootMod( 409 );      # largest primitive root for a prime less than 2000
21
gap> PrimitiveRootMod( 541, 2 );
10
gap> PrimitiveRootMod( 337, 327 ); # 327 is the largest primitive root mod 337
fail
gap> PrimitiveRootMod( 30 );       # there exists no primitive root modulo 30
fail
\endexample

\Declaration{IsPrimitiveRootMod}
\index{test!for a primitive root}
\index{prime residue group!generator}
\index{generator!of the prime residue group}

\beginexample
gap> IsPrimitiveRootMod( 2, 541 );
true
gap> IsPrimitiveRootMod( -539, 541 );  # same computation as above;
true
gap> IsPrimitiveRootMod( 4, 541 );
false
gap> ForAny( [1..29], r -> IsPrimitiveRootMod( r, 30 ) );
false
gap> # there is no a primitive root modulo 30
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Roots Modulo Integers}

\Declaration{Jacobi}
\index{quadratic residue}
\index{residue!quadratic}

\beginexample
gap> Jacobi( 11, 35 );  # 9^2 = 11 mod 35
1
gap> Jacobi( 6, 35 );   # it is -1, thus there is no r such that r^2 = 6 mod 35
-1
gap> Jacobi( 3, 35 );   # it is 1 even though there is no r with r^2 = 3 mod 35
1
\endexample

\Declaration{Legendre}
\index{quadratic residue}
\index{residue!quadratic}

\beginexample
gap> Legendre( 5, 11 );  # 4^2 = 5 mod 11
1
gap> Legendre( 6, 11 );  # it is -1, thus there is no r such that r^2 = 6 mod 11
-1
gap> Legendre( 3, 35 );  # it is -1, thus there is no r such that r^2 = 3 mod 35
-1
\endexample

\Declaration{RootMod}
\index{quadratic residue}
\index{residue!quadratic}
\index{root!of an integer modulo another}

\beginexample
gap> RootMod( 64, 1009 );  # note 'RootMod' does not return 8 in this case but -8;
1001
gap> RootMod( 64, 3, 1009 );
518
gap> RootMod( 64, 5, 1009 );
656
gap> List( RootMod( 64, 1009 ) * RootsUnityMod( 1009 ),
>          x -> x mod 1009 );  # set of all square roots of 64 mod 1009
[ 1001, 8 ]
\endexample

\Declaration{RootsMod}

\beginexample
gap> RootsMod( 1, 7*31 );  # the same as `RootsUnityMod( 7*31 )'
[ 1, 92, 125, 216 ]
gap> RootsMod( 7, 7*31 );
[ 21, 196 ]
gap> RootsMod( 5, 7*31 );
[  ]
gap> RootsMod( 1, 5, 7*31 );
[ 1, 8, 64, 78, 190 ]
\endexample

\Declaration{RootsUnityMod}
\index{modular roots}
\index{root!of 1 modulo an integer}

\beginexample
gap> RootsUnityMod( 7*31 );  RootsUnityMod( 3, 7*31 );
[ 1, 92, 125, 216 ]
[ 1, 25, 32, 36, 67, 149, 156, 191, 211 ]
gap> RootsUnityMod( 5, 7*31 );
[ 1, 8, 64, 78, 190 ]
gap> List( RootMod( 64, 1009 ) * RootsUnityMod( 1009 ),
>          x -> x mod 1009 );  # set of all square roots of 64 mod 1009
[ 1001, 8 ]
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Multiplicative Arithmetic Functions}

\Declaration{Sigma}

\beginexample
gap> Sigma( 1 );
1
gap> Sigma( 1009 );  # 1009 is a prime
1010
gap> Sigma( 8128 ) = 2*8128;  # 8128 is a perfect number
true
\endexample


\Declaration{Tau}

\beginexample
gap> Tau( 1 );
1
gap> Tau( 1013 );  # thus 1013 is a prime
2
gap> Tau( 8128 );
14
gap> Tau( 36 );  # the result is odd if and only if the argument is a perfect square
9
\endexample

\Declaration{MoebiusMu}

\beginexample
gap> MoebiusMu( 60 );  MoebiusMu( 61 );  MoebiusMu( 62 );
0
-1
1
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Continued Fractions}

\Declaration{ContinuedFractionExpansionOfRoot}

\beginexample
gap> x := Indeterminate(Integers);;
gap> ContinuedFractionExpansionOfRoot(x^2-7,20);
[ 2, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1 ]
gap> ContinuedFractionExpansionOfRoot(x^2-7,0);
[ 2, 1, 1, 1, 4 ]
gap> ContinuedFractionExpansionOfRoot(x^3-2,20);
[ 1, 3, 1, 5, 1, 1, 4, 1, 1, 8, 1, 14, 1, 10, 2, 1, 4, 12, 2, 3 ]
gap> ContinuedFractionExpansionOfRoot(x^5-x-1,50);
[ 1, 5, 1, 42, 1, 3, 24, 2, 2, 1, 16, 1, 11, 1, 1, 2, 31, 1, 12, 5, 1, 7, 11, 
  1, 4, 1, 4, 2, 2, 3, 4, 2, 1, 1, 11, 1, 41, 12, 1, 8, 1, 1, 1, 1, 1, 9, 2, 
  1, 5, 4 ]
\endexample

\Declaration{ContinuedFractionApproximationOfRoot}

\beginexample
gap> ContinuedFractionApproximationOfRoot(x^2-2,10);
3363/2378
gap> 3363^2-2*2378^2;
1
gap> z := ContinuedFractionApproximationOfRoot(x^5-x-1,20);
499898783527/428250732317
gap> z^5-z-1;
486192462527432755459620441970617283/
14404247382319842421697357558805709031116987826242631261357
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Miscellaneous}

\Declaration{TwoSquares}
\index{representation!as a sum of two squares}

\beginexample
gap> TwoSquares( 5 );
[ 1, 2 ]
gap> TwoSquares( 11 );  # there is no representation
fail
gap> TwoSquares( 16 );
[ 0, 4 ]
gap> TwoSquares( 45 );  # 3 is the minimal possible gcd because 9 divides 45
[ 3, 6 ]
gap> TwoSquares( 125 );  # it is not [5,10] because their gcd is not minimal
[ 2, 11 ]
gap> TwoSquares( 13*17 );  # [10,11] would be the other possible representation
[ 5, 14 ]
gap> TwoSquares( 848654483879497562821 );  # 848654483879497562821 is prime
#I  IsPrimeInt: probably prime, but not proven: 848654483879497562821
#I  FactorsInt: used the following factor(s) which are probably primes:
#I        848654483879497562821
[ 6305894639, 28440994650 ]
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                  
%E  numtheor.msk  . . . . . . . . . . . . . . . . . . . . . . . ends here