I'm thinking of a number, x, whose last 3 digits are somewhere between 400 and 500.

You could probably guess from those digits that it might be a square or a cube, but in fact it turns out to be both, and in fact the smallest possible such number.

What are the prime factors of x?

Extra credit: feeling adventurous, I next computed the smallest number, y, having the same last 3 digits, that was a seventh power, as well as a square and a cube.

What are the prime factors of y?

Brian, you should try wolframalpha.

In fact I used Excel for the first part to derive 531441 by inspection, comparing the cubes mod 1000 with a list of squares mod 1000.

But I could have used: x^6=441 mod 1000 when x == 9 || x == 241 || x == 259 || x == 491 || x == 509 || x == 741 || x == 759 || x == 991, giving 9^6, or 3^12 as the minimal solution.

Then for the second part, start with the idea that (1000a+b)^n, where b is some number between 0 and 999 factors to:1000a(various factors)+b^n, with no change in the last 3 digits of b^n.

x^7=441 mod 1000 gives x=721.

Then x^6=721 mod 1000 gives {x == 121 || x == 129 || x == 371 || x == 379 || x == 621 || x == 629 || x == 871 || x == 879}.

But if x^6 is 721 mod 1000 and x^(7*6) is 441 mod 1000, then x=121^42=11^84 is the minimal solution.

Edited on January 31, 2013, 9:11 am

Posted by broll on 2013-01-31 02:02:37