Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's have some number X which we will call "ending" or "suffix". How to find number which cubed have suffix or ending equal our X? I think good hint is that this number X always ends with odd number ( 1, 3, 7 ,9 )- no 5 here.

For example we have X = 123 and smallest number we are searching for is : 947, because 947^3 849278*123*.

How to deal with this problem and other similiar problems ? Chris

share|improve this question
6  
5^3 ends with 5. –  Did Jun 24 '11 at 10:02
    
Any number^3, where the number's LSD is 5 will end in 5. –  phant0m Jun 24 '11 at 11:05
    
For little operator work, make a column from 000 to 999 in column A of a spreadsheet, put =mod(A1^3,1000) in cell B1, and copy down. Then sort on column B and look for your target. –  Ross Millikan Jun 24 '11 at 18:14

2 Answers 2

up vote 5 down vote accepted

Assume that your suffix $X$ is coprime to $10$, because that makes the theory simpler (and you seem to want to do that anyway!). Basically you are looking for a way to find a cube root of $X$ modulo $10^n$, where $n$ is the number of digits in the suffix. If you know how to do modular powers quickly (see example below), then the following simple method works. The structure of the group of units of the ring $\mathbf{Z}/10^n\mathbf{Z}$ is well known. We use the following bit of information about that: the exponent of the group is $e=2^t5^{n-1}$, where the parameter $t=\max\{2,n-2\}.$ The exponent has the property that $X^e\equiv 1\pmod{10^n}$ for all $X$ coprime to $10$. So if we can find an integer $d$ such that $3d\equiv 1 \pmod e$, then the remainder of $Y=X^d$ modulo $10^n$ is the desired cube root. This follows from the calculation $$ Y^3\equiv X^{3d} \equiv X^{ke+1}=(X^e)^kX\equiv X \pmod{10^n}, $$ where $k$ is the integer such that $3d=ke+1$. Finding a number $d$ is easy, because always either $e+1$ or $2e+1$ will be divisible by $3$.

As an example consider the cases $n=2$ and $n=3$. When $n=2$ we get $e=20$, and we observe that $d=7$ works, because $3\cdot7=21\equiv 1\pmod{20}.$ Let's test. Choose $X=03$. Then $3^7=2187\equiv 87 \pmod{100},$ so the theory says that $87$ should work. Indeed, $87^3=658503$. When $n=3$, then $e=100$, and we can choose $d=67$ as $3\cdot67=201\equiv 1\pmod{100}.$ Thus we can recover your example case by computing the remainder of $123^{67}$ modulo $1000$. By repeated squaring (all the congruences modulo $1000$) we get that $123^2\equiv 129$, $123^4\equiv129^2\equiv641$, $\ldots$, $123^{64}\equiv241$, so in the end we get $$ 123^{67}\equiv 123^{64+2+1}\equiv 123\cdot129\cdot241\equiv 947\pmod{1000}, $$ rederiving your answer.

It is perfectly possible to also find the (modular) cube root one digit at a time as is outlined in Mark Bennet's answer.

share|improve this answer
    
Thanks a lot ! Very clear explaination ! –  Chris Jun 24 '11 at 18:07
    
This is neat, and illuminates the structure.. –  Mark Bennet Jun 24 '11 at 19:05

Note: in base 10 any digit can be the final digit of a cube.

Work on the least significant digits first.

$0^3=0; 1^3=1; 2^3=8; 3^3=27; 4^3=64, 5^3=125; 6^3=216; 7^3=343; 8^3=512; 9^3=729$

Choose a digit $a$ so that $a^3$ ends with the digit you need, this will be unique.

Then use $(10b+a)^3 = ... +30a^2b+a^3$ to choose $b$ to fix the final two digits - which may not be possible, and it is possible that there will be more than one $b$ to test.

Then $(100c+10b+a)^3= ... 300c(10b+a)^2+(10b+a)^3$ will deal with the hundreds digit ... etc

Exploring the various possibilities will give you some clues as to what works and why.

share|improve this answer
    
Thanks a lot ! Nice explaination and method –  Chris Jun 24 '11 at 18:08
    
This probably has a lower computational complexity than the method outlined in my answer. –  Jyrki Lahtonen Jun 26 '11 at 19:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.