1
$\begingroup$

I'm looking for ways to know that a given number $N$ cannot be a cube. If $N=n^3$, there is a one-to-one mapping between the last digit of $n$ and the last digit of $N$ - that is, the last digit of a cube can be anything.

The last two digits however, have some strings attached. For instance it seems that a cube cannot end with certain digit pairs (I think): $$ 14,15,18,20\ ...$$

My question is, for a given $m$ last digits of a cube $n^3$:

  1. How many of the $10^m$ theoretically possible combinations can actually appear?
  2. Is there a fast way of computing these without brute forcing?
$\endgroup$
  • 1
    $\begingroup$ The following 37 pairs cannot appear as the last two digits of a cube: $02, 05, 06, 10, 14, 15,$ $ 18, 20, 22, 26, 30, 34, $ $ 35, 38, 40, 42, 45, 46, $ $ 50, 54, 55, 58, 60, 62, 65, $ $ 66, 70, 74, 78, 80, 82, 85, $ $ 86, 90, 94, 95, 98$. Every other pair does appear. $\endgroup$ – MJD Jul 2 '13 at 6:24
  • $\begingroup$ @MJD - care to explain the methodology? can one extend it to $m$ digits? $\endgroup$ – nbubis Jul 2 '13 at 6:27
  • $\begingroup$ Calculate the last two digits of every cube from $00^3\ldots 99^3$ and see what is omitted. It's enough to go up to $99^3$, since the last two digits of $n^3$ and $(100 + n)^3$ are always the same. I thought this was what you mean by "brute forcing". If it's not what you meant, you should explain what you did mean. $\endgroup$ – MJD Jul 2 '13 at 6:30
  • $\begingroup$ Ok, that's the brute force way I originally had, but I missed out on the 01. is there a smarter way? Can the number be known without calculated all of them? $\endgroup$ – nbubis Jul 2 '13 at 6:35
  • 1
    $\begingroup$ oeis.org/A046638 $\endgroup$ – MJD Jul 2 '13 at 6:39
1
$\begingroup$

The usual fast way is by modular arithmetic. For 10, the significant numbers are 2 and 5, which cube to give 8 and 125.

For $2$, all even numbers give a cube that is $0$ mod $8$. The odd numbers cube to themselves, modulo 8, so the valid answers modulo 8, are $0, 1, 3, 5, 7$, ie $5/8$ of the total.

For $5$, all multiples of $5$ cube to a multiple of $125$, but the remaining numbers are freely occurable. For example, there is a number whose cube is $3$, mod $125$. So for $5$, there are $100+1$ possible endings, or $101/125$.

Over $1000$, then there are $5/8 * 101/125$ = $505/1000$. For $100$, one reduces the case for 2 to modulo $4$, ie $0, 1, 3$, and for $5$, it's modulo $25$ (ie 21 solutions). There are thus $63=3*21$ possible endings for this.

When the fifth power is involved, a different thing happens. The powers of 5 must (in base 5), end in the digits $00,\; 01,\; 12,\; 33,\; 44$ only. The powers of $2$ are identical to above. So there are just $5$ possible endings for $25$ and $3$ possible endings for $4$, or just $15$ possible endings for $100$.

The ultimate form of this leads to the four cases where $10^a \mid x^n-x$, ie $-0001$, $-0000$, $-0625$ and $9376$, as the numbers $2$ and $5$ divide the value $x$.

When one handles a base with $3$ prime divisors, one does this for each of the three divisors.

Details

The process is weakly multiplicative. That means, if $x$ and $y$ are co-prime (ie $\operatorname{gcd}(x,y)=1$, then $f(xy)=f(x)\cdot f(y)$

Consider for example, the squares, modulo 20. This is weakly multiplicative, since we can write $f(20)=f(5) f(4)$, but not $f(20)=f(2) f(10)$. These are fairly easy to enumerate, since they all occur singly in the first six squares ($0$ to $5$).

                                                  0   1   4
     0    1    2    3    4    5              0    0  16   4
     0    1    4    9   16    5 =  6         1    5   1   9
                                    Rows = mod 4, columns = mod 5

There are also 6 for modulo 15, which gives

                                                 0    1    4
     0    1    2    3   4    5    6          0   0    6    9
     0    1    4    9   1   10    6          1  10    1    4
                                    Rows = mod 3,  columns = mod 5

One sees that the modulo against $5$ does not depend on the other factors of the base. Moreover, there is a full column of the other primes for each case of 5. We can deal with the individual prime powers separately. So when we disect 10 or 14 below, instead of dealing with the full number, we can deal with the prime powers separately, and multiply the lot together.

One really has to worry if $\operatorname{gcd}(n, p^2-p) > 1$. In this case, there is a reduction of available choices.

For multiples of $p$, there is only one solution up to $p^n$ (ie -$0000000$ base $p$

When the gcd is $p$, then some $p^m$ divides $n$, and then there is only one string of $m+1$ digits, base $p$, for each primitive digit of $p$.

When the gcd ($x$) divides $p-1$, then there are just $(p-1)/x$ possible endings for non-multiples of $p$.

To give an example, suppose the power is $14$, and we're dealing with a base of 14. What is the count the available digits that $x^14$ might end in base $14$?

For prime $7$, the first rule tells us that all multiples of $7$ end in $00$ base $7$. This means that 1/7 of all numbers give rise to just 1 ending.

The second rule tells us that 7 divides $\operatorname{gcd}(14, 7^2-7)$. This means that there are just $7$ possible endings for 7th powers in base 7 (ie $00$, $01$, $24$, $25$, $42$, $43$ and $66$). We see that $6/7$ of the possible endings are removed, whether or not we count $00$: it's the same for each place.

The third rule tells us that 2 divides $\operatorname{gcd}(14, 7^2-7)$, so just half of the numbers (ie 3) are squares. These are $1$, $2$ and $4$.

All together, the modulo-7 restriction tells us that the only solutions for this problem, is that it is one of $1 + 42/7/2 = 4$ answers: here $00$, $01$, $24$ and $42$, base $7$

For $2$, the same rules tells us that there are just two answers over modulo $4$, that is, $00$ and $01$, base $2$

The chineses remainder solution can be used to find these $4*2=8$ solutions.

$\endgroup$
  • $\begingroup$ Could you explain what you mean by "for 2" "for 5" etc.? $\endgroup$ – nbubis Jul 2 '13 at 22:15
  • $\begingroup$ I added further text in the 'details', to show how the separate primes can be teased out and processed separately. Thanks. $\endgroup$ – wendy.krieger Jul 3 '13 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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