Ask Your Question

Symbolic integer arithmetic

asked 2014-07-28 15:41:10 +0200

Dirk Danckaert gravatar image

updated 2014-07-28 20:36:28 +0200

It's not that hard to find a closed expression for the remainder of the polynomial $x^n$ modulo $x^2-5x-2$. But I don't seem to manage it in SAGE.


works as expected, but replacing the last line with a^n gives an error (non-integral exponents not supported). I understand a general variable is not a SAGE integer, but how DO I make clear n is supposed to be an integer?

In the same way, it's not that hard to calculate the symbolic n-the power of a small, say 2x2, matrix, but the straightforward aproach of simplifying A^n gives the same error (non-integral exponents not supported).

I checked wolfram alpha for the symbolic power of a matrix, and immediately got the expected answer for [[1,2],[3,4]]^n .

Wolfram alpha answer

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2014-07-28 17:39:38 +0200

rws gravatar image

updated 2014-07-29 08:12:13 +0200

Well looking at [a^n for n in range(10)] it's obviously a linear recurrence with the coefficients (5,2) the coefficients of mp,

a^n mod mp = p(n)*a+q(n), where p(n)=A015535(n), q(n)=2p(n-1)

and this generalizes to any polynomial. So, your question concerns two things:

  • have Sage understand your problem. I don't think that simply giving the expression a^n mod mp should output a closed form of that result. Rather, Sage would need a hint, like a command that takes that expression a^n and the ring and returns an expression containing linear recurrence (linrec) objects,
  • Sage would need a linear recurrence object, this is, see also
  • to compute the values of degree-2 linrecs you can already use lucas_number1 but this is no general solution, and it's not a symbolic function in Sage, so it cannot be part of a returned expression

There may be an algebraic solution but, alas, I'm not an algebraist.

Short of an immediate solution, you can use the general Binet formula with 2-degree polynomials and 2x2 matrices to get the closed form in terms of elementary functions:

def GBinet(c,d,a0,a1,n):
    return ((a1-c*a0+a0*r1)*r1^n-(a1-c*a0+a0*r2)*r2^n)/sqrt(c^2+4*d)

sage: n=var('n')
sage: p(n)=GBinet(5,2,0,1,n)
sage: p(n)
-1/33*sqrt(33)*((-4/(sqrt(33) + 5))^n - (4/(sqrt(33) - 5))^n)
sage: p(5).n()
edit flag offensive delete link more


Well, as a matter of fact, I think it should output a closed form. I'm approaching the question from a didactical point of view. It may well be that treating these questions as linear recurrences is a more fundamental point of view, but students and even many teachers are not aware of that. I checked Wolfram Alpha, and that gives the closed form answer straight away. I just want to know how I can prod SAGE to do something along the same lines.

Dirk Danckaert gravatar imageDirk Danckaert ( 2014-07-28 20:32:52 +0200 )edit

I have added the Binet formula (that's what Wolfram prints) to my answer.

rws gravatar imagerws ( 2014-07-29 08:14:05 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2014-07-28 15:41:10 +0200

Seen: 457 times

Last updated: Jul 29 '14