[superprismatic]

Consider polynomials which have coefficients

taken modulo 7. So the polynomials

18x¹² - 4x⁵ + x - 1 and 4x¹² + 3x⁵ + x + 6

are equivalent. Note that the exponents are

not taken modulo 7. One such polynomial is:

P[x] = x⁶ + 4x⁵ + x⁴ + 2x³ + 3x² + 6x + 5.

Can you find a polynomial multiple of P[x]

which is a trinomial and has the smallest

possible degree?

[Guest]

i know there has to be a logical mathematical way to do this right, not just trial and error? im not that patient

[superprismatic]

i know there has to be a logical mathematical way to do this right, not just trial and error? im not that patient

There are better ways to do it than trial and error. I think they all require a bit too much work than you can

do by hand. I think you really need to program a spreadsheet or use a proper programming language to do the

calculations. Once you figure out a way to do it, you'll most likely need a computer to do the grunt work for

you. Of course, someone might figure out a way to do it by hand, but I doubt it.

[superprismatic]

In case someone needs it, here's a hint on how to proceed.

Since we are looking for a multiple of P[x], we are actually looking for a polynomial which is 0 modulo P[x]. Whatever the polynomial is, we can subtract as many copies

of P[x] from it without changing its value modulo P[x]. So, P[x] is actually 0 as far as looking at polynomials modulo P[x] goes. Thus, x⁶ + 4x⁵ + x⁴ + 2x³ + 3x² + 6x + 5 = 0.

Then, x⁶ = -4x⁵ - x⁴ - 2x³ - 3x² - 6x - 5, or, x⁶ = 3x⁵ + 6x⁴ + 5x³ + 4x² + x + 2. This allows us to compute all larger powers of x in terms of powers less than 6 as follows:

x⁷ = x(3x⁵ + 6x⁴ + 5x³ + 4x² + x + 2) = 3x⁶ + 6x⁵ + 5x⁴ + 4x³ + x² + 2x = 3(3x⁵ + 6x⁴ + 5x³ + 4x² + x + 2) + 6x⁵ + 5x⁴ + 4x³ + x² + 2x. Multiplying and combining mod 7 gives

x⁷ = x⁵ + 2x⁴ + 5x³ + 6x² + 5x + 6. In the same way, we can compute x⁸, x⁹, x¹⁰, ...... (as far as we want) in terms of powers of x from x⁰ to x⁵. Thus, we can easily

compute the remainder of any power of x when divided by P[x].

[araver]

 Q[X]=X^166+4*X^137+6[/CODE]

[/spoiler]

[superprismatic]

araver's got it!

If anyone is still interested in this problem but doesn't want to follow

in araver's footsteps, here is a slightly different but related problem:

Find the smallest degree trinomial multiple of P[x] all of whose nonzero

coefficients are 1.