IBM Research | Ponder This | May 2013 solutions
Skip to main content

May 2013

<<April May June>>



The intended solution was to factor 1+x+x^2+x^4 to (x^2+ax+b)(x^2+cx+d) modulo 2233393.
Note that 2233393 = 19*41*47*61, so we can factor modulo each one of the four primes and combine the resulting coefficients using the Chinese remainder theorem.
A possible answer is
y=x*x
a=638773*x
a=y+a
a=1613501+a
b=1594620*x
b=y+b
b=b+1831287
z=a*b
z=z mod 2233393

As for the bonus question - it's the June 2012 question from the UYHIP web site. Visit the site on July to learn about their solution.



If you have any problems you think we might enjoy, please send them in. All replies should be sent to: webmster@us.ibm.com