1

Consider numbers written in base $b$, where $x\leq q\leq z$. For which bases $q$ $n^2$ ends with if $n$ ends with $0$.

user65422
  • 1,123

3 Answers3

2

Hint: For any base $b$, things will go bad if there is a positive integers $x$ such that $x^2$ is divisible by $b$ but $x$ isn't. For example, $30^2$ is divisible by $50$ but $30$ isn't, so things will go bad for base $50$.

Added: Let us think about the specific bases $5$ to $9$. Let's see what we need to make sure that if $n^2$ ends in $0$, then $n$ ends in $0$. To say that $n^2$ ends in $0$ is just to say that the base $b$ divides $n^2$. To say that $n$ ends in $0$ just says $b$ divides $n$.

So we ask for the various bases, when does $b$ divides $n^2$ force $b$ divides $n$?

Case $b=5$: If $5$ divides $n^2$, does $5$ divide $n$? Sure. After all, $5$ is prime.

Case $b=6$: If $6$ divides $n^2$, does $6$ divide $n$? If $6$ divides $n^2$, then $2$ divides $n^2$ and $3$ divides $n^2$. But then $2$ divides $n$ and $3$ divides $n$, so $6$ divides $n$.

Case $b=7$: same reasoning as for $5$: if $7$ divides $n^2$ then $7$ divides $n$.

Case $b=8$: This one is different. Let $n=4$. Then $8$ divides $n^2$ but $8$ does not divide $n$.

Case $b=9$: This is like $b=8$. Let $n=6$. Then $9$ divides $n^2$ but $9$ does not divide $n$.

Generalization: The "bad" bases $8$ and $9$ are each divisible by a perfect square greater than $1$. Call a positive integer $b$ square-free if no perfect square $\gt 1$ divides $b$. If $b$ is square-free, like $b=10$, then if $n^2$ in base $b$ ends in a $0$, then so does $n$.

If $b\gt 1$ is not square-free, there will be some $n$ such that in base $b$, the number $n^2$ ends in a $0$, but $n$ does not.

André Nicolas
  • 507,029
  • I'm trying to wrap my head around your example. So how do is $30^2$ translated into a base 50? – user65422 Mar 21 '13 at 00:13
  • Let's not worry about the details of the translation. We will want to express $30^2$ as $a_1\cdot 50^1+a_0$ where $a_1$ and $a_0$ are "digits." Since $50$ divides $300$, we will have $a_0=0$. I will add to my hint in about $10$ minutes, since you have been thinking about this for a while. – André Nicolas Mar 21 '13 at 00:22
1

Note this example in hex. You have 0x4${}^2$ = 0x10. It's not in your range, but it should tell you something.

ncmathsadist
  • 49,383
0

Consider why this is true of base 10:

Ending in 0 means that a number is a multiple of 10. Thus, its prime factorization includes 2*5.
How does squaring affect the prime factorization?

user1992284
  • 413