Un algoritmo para resolver el problema de Frobenius utilizando bases de Gröbner

Abstract

RESUMEN: Sea A = {a1, a2, . . . , ak} un conjunto de enteros positivos primos relativos entre sí. Dado un ente- ro positivo N, se dice que N es representable por A si existen enteros no negativos x1, x2, . . . , xk tales que N = Pki=1 aixi. El Problema de Frobenius consiste en encontrar el mayor entero, denotado con g(A), que no es representable por A. En este artículo se presenta un algoritmo para resolver el problema de Frobenius utilizando bases de Gröbner. Al final, en el Apéndice, se presentan los algoritmos desarrollados en este trabajo implementados en el sistema de álgebra computacional MuPAD.

ABSTRACT: Let A = {a1, a2, . . . , ak} be a set of relatively positive prime integers, a positive integer N is called representable by A if exists non-negatives integers x1, x2, . . . , xk, such that N =Pki=1 aixi. The Frobenius Problem consits in determining the largest integer, denoted with g(A), that is not representable by A. In this work we present an algorithm to solve the Frobenius Problem using Gröbner Bases. In the Apendix we present the algorithms developed in this work, implemented in the computer system algebra MuPAD.