You might remember that for any integer greater than 1, is a if its factors are 1 and itself. The integers 2, 3, 5, and 7 are primes, but 9 is not prime because . The command primep() is useful for testing whether or not an integer is prime:
Let’s now define a function called primes_first_n() in to return a list of the first primes, where is a positive integer. Programming in the Maxima language is different from programming in other languages like ,, and . For example, if your variable is be assigned a number, you don’t need to define whether your variable is of type int, long, double, or bool. All you have to do is use the colon operator “:” to assign some value to a variable, like in the following example.
(%i50) num : 13$
(%i51) num;
(%o51) 13
(%i52) str : "my string"$
(%i53) str;
(%o53) my string
(%i54) L : ["a", "list", "of", "strings"]$
(%i55) L;
(%o55) [a, list, of, strings]
Before defining the function primes_first_n(), there are two useful built-in Maxima functions that you should know about. These are append() and last(). The function append() can be used to append an element to a list, whereaslast() can be used to return the last element of a list:
Below is the function primes_first_n() which pulls together the features of next_prime(n), append(), and last(). Notice that it is defined at the Maxima command line interface.
(%i60) primes_first_n(n) := (
if n < 1 then
[]
else (
L : [2],
for i:2 thru n do (
L : append(L, [next_prime(last(L))])
),
L
)
)$
You can also put the above function inside a text file called, say, /home/mvngu/primes.mac with the following content:
/* Return the first n prime numbers.
*
* INPUT:
*
* - n -- a positive integer greater than 1.
*
* OUTPUT:
*
* - A list of the first n prime numbers. If n is less than 1, then return
* an empty list.
*/
primes_first_n(n) := (
if n < 1 then
[]
else (
L : [2],
for i:2 thru n do (
L : append(L, [next_prime(last(L))])
),
L
)
)$
Like C++ and Java, Maxima also uses “/*” to denote the beginning of a comment block and “*/” to denote the end of a comment block. To load the content of the file /home/mvngu/primes.mac into Maxima, you use the command load(). Let’s load the above file and experiment with the custom-defined function primes_first_n():
Integer is about breaking up an integer into smaller components. In , these smaller components are usually the prime factors of the integer. Use the command ifactors() to compute the prime factors of positive integers:
The prime factors of 10 are and . When you multiply these two prime factors together, you end up with . The expression is called the prime factorization of 10. Similarly, the expression is the prime factorization of 25, and is the prime factorization of 72.
Greatest common divisors
Closely related to integer factorization is the concept of (GCD). The Maxima commandgcd() is able to compute the GCD of two expressions and where this makes sense. These two expressions may be integers, polynomials, or some objects for which it makes sense to compute their GCD. For the moment, let’s just work with integers:
The GCD of two integers and can be recursively defined as follows:
where is the remainder when is divided by . The above recursive definition can be easily translated to a Maxima function for integer GCD as follows (credit goes to for the Maxima code):
/* Return the greatest common divisor (GCD) of two integers a and b.
*
* INPUT:
*
* - a -- an integer
* - b -- an integer
*
* OUTPUT:
*
* - The greatest common divisor of a and b.
*/
igcd(a, b) := block(
if b = 0 then
return(a)
else
return( igcd(b, mod(a,b)) )
);
Save the above code to a text file and load it first before using the function. Or you can define the function from the Maxima command line interface and proceed to use it:
(%i5) igcd(a, b) := block(
if b = 0 then
return(a)
else
return( igcd(b, mod(a,b)) )
)$
(%i6) igcd(9, 12);
(%o6) 3
(%i7) igcd(21, 49);
(%o7) 7
(%i8) igcd(22, 11);
(%o8) 11
The provides an interesting relationship between , and the pair and . Here is a Maxima function definition courtesy of amca:
/* Apply the extended Euclidean algorithm to compute integers s and t such
* that gcd(a,b) = as + bt.
*
* INPUT:
*
* - a -- an integer
* - b -- an integer
*
* OUTPUT:
*
* - A triple of integers (s, t, d) satisfying the relationship
* d = gcd(a,b) = as + bt. This algorithm does not guarantee that s and t
* are unique. There may be other pairs of s and t that satisfy the requirement.
*/
igcdex(a,b) := block(
[d, x, y, d1, x1, y1],
if b = 0 then
return([1, 0, a])
else (
[x1, y1, d1] : igcdex(b, mod(a,b)),
[x, y, d] : [y1, x1 - quotient(a,b)*y1, d1],
return([x, y, d])
)
);
Or you can define it from the Maxima command line:
(%i9) igcdex(a,b) := block(
[d, x, y, d1, x1, y1],
if b = 0 then
return([1, 0, a])
else (
[x1, y1, d1] : igcdex(b, mod(a,b)),
[x, y, d] : [y1, x1 - quotient(a,b)*y1, d1],
return([x, y, d])
)
)$
Let’s use the function igcdex() for various pairs of integers and verify the result.
Hello!If i want to make the extended Euclidean algorithm for polynomials what chabges should i do?i can not understant how i define polynomials. I am little confused!I also want to ask if you have a good online manual for maxima.Thanks for your help.
The following Maxima function implements the Chinese remainder theorem:
crt(A, M) := block(
Mprod : product(M[i], i, 1, length(M)),
Mdiv : map(lambda([x], Mprod / x), M),
X : map(inv_mod, Mdiv, M),
x : sum(A[i]*X[i]*Mdiv[i], i, 1, length(M)),
return(mod(x, Mprod))
)$
The list A contains integers you want to solve for, and M is a list of moduli. Here are some examples on using the function crt():
Elementary number theory using Maxima
-- mvngu
Prime numbers
You might remember that for any integer![n]( "n")
greater than 1, ![n]( "n")
is a if its factors are 1 and itself. The integers 2, 3, 5, and 7 are primes, but 9 is not prime because 
. The command primep() is useful for testing whether or not an integer is prime:
And the command next_prime(n) returns the next prime number greater than or equal to![n]( "n")
:
Let’s now define a function called primes_first_n() in to return a list of the first![n]( "n")
primes, where ![n]( "n")
is a positive integer. Programming in the Maxima language is different from programming in other languages like ,, and . For example, if your variable is be assigned a number, you don’t need to define whether your variable is of type int, long, double, or bool. All you have to do is use the colon operator “:” to assign some value to a variable, like in the following example.
Before defining the function primes_first_n(), there are two useful built-in Maxima functions that you should know about. These are append() and last(). The function append() can be used to append an element to a list, whereaslast() can be used to return the last element of a list:
Below is the function primes_first_n() which pulls together the features of next_prime(n), append(), and last(). Notice that it is defined at the Maxima command line interface.
(%i60) primes_first_n(n) := ( if n < 1 then [] else ( L : [2], for i:2 thru n do ( L : append(L, [next_prime(last(L))]) ), L ) )$You can also put the above function inside a text file called, say, /home/mvngu/primes.mac with the following content:
/* Return the first n prime numbers. * * INPUT: * * - n -- a positive integer greater than 1. * * OUTPUT: * * - A list of the first n prime numbers. If n is less than 1, then return * an empty list. */ primes_first_n(n) := ( if n < 1 then [] else ( L : [2], for i:2 thru n do ( L : append(L, [next_prime(last(L))]) ), L ) )$Like C++ and Java, Maxima also uses “/*” to denote the beginning of a comment block and “*/” to denote the end of a comment block. To load the content of the file /home/mvngu/primes.mac into Maxima, you use the command load(). Let’s load the above file and experiment with the custom-defined function primes_first_n():
(%i64) load("/home/mvngu/primes.mac"); (%o64) /home/mvngu/primes.mac (%i65) primes_first_n(0); (%o65) [] (%i66) primes_first_n(-1); (%o66) [] (%i67) primes_first_n(-2); (%o67) [] (%i68) primes_first_n(1); (%o68) [2] (%i69) primes_first_n(2); (%o69) [2, 3] (%i70) primes_first_n(3); (%o70) [2, 3, 5] (%i71) primes_first_n(10); (%o71) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]Factorizing integers
Integer is about breaking up an integer into smaller components. In , these smaller components are usually the prime factors of the integer. Use the command ifactors() to compute the prime factors of positive integers:
The prime factors of 10 are
and 
. When you multiply these two prime factors together, you end up with 
. The expression 
is called the prime factorization of 10. Similarly, the expression 
is the prime factorization of 25, and 
is the prime factorization of 72.
Greatest common divisors
Closely related to integer factorization is the concept of (GCD). The Maxima commandgcd() is able to compute the GCD of two expressions![e_1]( "e_1")
and ![e_2]( "e_2")
where this makes sense. These two expressions may be integers, polynomials, or some objects for which it makes sense to compute their GCD. For the moment, let’s just work with integers:
The GCD of two integers![a]( "a")
and ![b]( "b")
can be recursively defined as follows:
where
is the remainder when ![a]( "a")
is divided by ![b]( "b")
. The above recursive definition can be easily translated to a Maxima function for integer GCD as follows (credit goes to for the Maxima code):
/* Return the greatest common divisor (GCD) of two integers a and b. * * INPUT: * * - a -- an integer * - b -- an integer * * OUTPUT: * * - The greatest common divisor of a and b. */ igcd(a, b) := block( if b = 0 then return(a) else return( igcd(b, mod(a,b)) ) );Save the above code to a text file and load it first before using the function. Or you can define the function from the Maxima command line interface and proceed to use it:
(%i5) igcd(a, b) := block( if b = 0 then return(a) else return( igcd(b, mod(a,b)) ) )$ (%i6) igcd(9, 12); (%o6) 3 (%i7) igcd(21, 49); (%o7) 7 (%i8) igcd(22, 11); (%o8) 11The provides an interesting relationship between
, and the pair ![a]( "a")
and ![b]( "b")
. Here is a Maxima function definition courtesy of amca:
/* Apply the extended Euclidean algorithm to compute integers s and t such * that gcd(a,b) = as + bt. * * INPUT: * * - a -- an integer * - b -- an integer * * OUTPUT: * * - A triple of integers (s, t, d) satisfying the relationship * d = gcd(a,b) = as + bt. This algorithm does not guarantee that s and t * are unique. There may be other pairs of s and t that satisfy the requirement. */ igcdex(a,b) := block( [d, x, y, d1, x1, y1], if b = 0 then return([1, 0, a]) else ( [x1, y1, d1] : igcdex(b, mod(a,b)), [x, y, d] : [y1, x1 - quotient(a,b)*y1, d1], return([x, y, d]) ) );Or you can define it from the Maxima command line:
(%i9) igcdex(a,b) := block( [d, x, y, d1, x1, y1], if b = 0 then return([1, 0, a]) else ( [x1, y1, d1] : igcdex(b, mod(a,b)), [x, y, d] : [y1, x1 - quotient(a,b)*y1, d1], return([x, y, d]) ) )$Let’s use the function igcdex() for various pairs of integers and verify the result.
Hello!If i want to make the extended Euclidean algorithm for polynomials what chabges should i do?i can not understant how i define polynomials. I am little confused!I also want to ask if you have a good online manual for maxima.Thanks for your help.
> Hello!If i want to make the extended Euclidean algorithm
> for polynomials what chabges should i do?i can not understant
> how i define polynomials.
You should direct this question to the Maxima mailing list. See
> I am little confused!I also want to ask if you have a
> good online manual for maxima.Thanks for your help.
You should consult the documentation on the Maxima website. See
http://maxima.sourceforge.net/documentation.html
Thanks but i have already solved my problem.Thanks for your help!!!
Hello!Can anyone tell me if there is a function in maxima about the chinese remainder theorem?Thanks for your time!
Hi Konstantinos,
The following Maxima function implements the Chinese remainder theorem:
crt(A, M) := block( Mprod : product(M[i], i, 1, length(M)), Mdiv : map(lambda([x], Mprod / x), M), X : map(inv_mod, Mdiv, M), x : sum(A[i]*X[i]*Mdiv[i], i, 1, length(M)), return(mod(x, Mprod)) )$The list A contains integers you want to solve for, and M is a list of moduli. Here are some examples on using the function crt():
%i1) load("crt.mac"); (%o1) crt.mac (%i2) A : [2, 3, 1]$ (%i3) M : [3, 4, 5]$ (%i4) x : crt(A, M); (%o4) 11 (%i5) mod(x, 3); (%o5) 2 (%i6) mod(x, 4); (%o6) 3 (%i7) mod(x, 5); (%o7) 1 (%i8) A : [4, 7, 3]$ (%i9) M : [5, 8, 9]$ (%i10) x : crt(A, M); (%o10) 39 (%i11) mod(x, 5); (%o11) 4 (%i12) mod(x, 8); (%o12) 7 (%i13) mod(x, 9); (%o13) 3Thanks a lot for your help!!!!
相关链接：
Categories:documentation, Maxima, number theory, programming, symbolic computationTags:computer algebra system, mathematics, maxima, number theory, open source software,programming, symbolic computation