26
$\begingroup$

Please help me with solving this :
prove that none of $\{11, 111, 1111 \ldots \}$ is the square of any $x\in\mathbb{Z}$ (that is, there is no $x\in\mathbb{Z}$ such that $x^2\in\{11, 111, 1111, \ldots\}$).

$\endgroup$

10 Answers 10

50
$\begingroup$

Hint: Perfect squares are not of the form $4k+3$, where $k$ is an integer.


Hint: For an even integer, $n=2j$, then $n^2 = (2j)^2 = ??$ For an odd integer, $n=2j+1$, then $n^2 = (2j+1)^2 = ??$.

$\endgroup$
  • $\begingroup$ this is intuitive but how do i prove this? $\endgroup$ – user45099 Feb 8 '13 at 19:34
  • $\begingroup$ do you know why Perfect squares are not of the form 4k+3 ? $\endgroup$ – Pechenka Feb 8 '13 at 19:35
  • 9
    $\begingroup$ @Pechenka Because $n^2 \bmod 4$ can only be $0$ or $1$ $\endgroup$ – Sasha Feb 8 '13 at 19:38
  • 2
    $\begingroup$ @DramaFreak If you explain what additional detail you need / don't understand, that might be better than simply posting a bounty. $\endgroup$ – Calvin Lin Jun 18 '13 at 23:02
15
+25
$\begingroup$

A square number can never end with two odd digits

If it did it would have to be the square of an odd number $x = 10a+b$ where $b$ is odd.

$x^2 = 100a^2 + 20ab + b^2$ so you just have to check for $x = 1,3,5,7$ or $9$ that the 10s digit is even and the rest follow.

$\endgroup$
15
$\begingroup$

Let suppose that there exists a number that squared gives $11 \cdots111$. Let $ba$ be its last two digits. Then either $a=1$ or $a=9$.

But if $a=1$, then the tens digit is $b + b \pmod{10}$ , which is even.

If $a=9$, , then the tens digit is $9 b + 8 + 9 b \pmod{10} = 18 b + 8 \pmod{10}$; which is also even.

Then, the tens digit cannot be $1$.

By the same reasoning, you can get the stronger result (see Philip Gibbs' answer) that a square cannot end with two odd digits.

$\endgroup$
  • $\begingroup$ Why did you use this approach? $\endgroup$ – Username Unknown Jun 12 '13 at 18:03
  • 4
    $\begingroup$ @DramaFreak What do you mean? Why not? $\endgroup$ – leonbloy Jun 12 '13 at 18:20
  • $\begingroup$ Where does $b+8+9b=1$ come from? $(xyzw...b9)^2$ has tens digit $(2\cdot9\cdot b+b^2)=8b+b^2\bmod 10$, but I don't see where that equates at all to the posed expression. The congruency to $8\pmod{10}$ suggests that every number ending in $9$ has a square that ends in $81$, which clearly isn't true. $\endgroup$ – Steven Stadnicki Jun 18 '13 at 22:32
  • $\begingroup$ @StevenStadnicki: Yes, there was an error (also in your formula), I hope it's better now. $\endgroup$ – leonbloy Jun 18 '13 at 23:52
  • $\begingroup$ @leonbloy Looks much better - I spaced that of course $b^2$ appears in the hundreds' place, not the tens'. $\endgroup$ – Steven Stadnicki Jun 19 '13 at 0:04
9
$\begingroup$

Every integer is of one of the forms $\color{green}4k$, $\color{green}4k+\color{red}1$, $\color{green}4k+\color{red}2$ or $\color{green}4k+\color{red}3$ with $k$ integer. The square of an integer has therefore one of the forms

  • $(\color{green}4k)^2 = 16k^2 = \color{green}4(4k^2) = \color{green}4k_0$,
  • $(\color{green}4k+\color{red}1)^2 = 16k^2+8k+1 = \color{green}4(4k^2+2k)+\color{red}1 = \color{green}4k_1+\color{red}{1}$,
  • $(\color{green}4k+\color{red}2)^2 = 16k^2+16k+4 = \color{green}4(4k^2+4k+1)=\color{green}4k_2$ or
  • $(\color{green}4k+\color{red}3)^2 = 16k^2+24k+9 = \color{green}4(4k^2+6k+2)+\color{red}1 = \color{green}4k_3+\color{red}1$.

That is, a perfect square is equivalent either to $\color{red}0$ or to $\color{red}1$ modulo $\color{green}4$.

On the other hand, $R_n=\underbrace{1\ldots1}_n=(10^n-1)/9$ for $n>1$ has the form

  • $R_n=100R_{n-2}+11 = \color{green}4(25R_{n-2}+2)+\color{red}3 = \color{green}4k_r+\color{red}3$.

That is, for $n>1$, $R_n$ is equivalent to $\color{red}3$ modulo $\color{green}4$, which as shown above does not happen for perfect squares.

$\endgroup$
7
$\begingroup$

If $n\equiv11\pmod{100}$, then $$ \begin{align} n &=100k+11\\ &=4(25k+2)+3\\ &\equiv3\pmod{4} \end{align} $$ If $n$ is even, $n=2k$ and $n^2=4k^2$. Thus, $n^2\equiv0\pmod{4}$.
If $n$ is odd, $n=2k+1$ and $n^2=4(k^2+k)+1$. Thus, $n^2\equiv1\pmod{4}$

Therefore, whether $n$ is even or odd, $n^2\not\equiv3\pmod{4}$, and consequently, $$ n^2\not\equiv11\pmod{100} $$

$\endgroup$
  • $\begingroup$ Would the downvoter care to comment? Is there something wrong with this answer? $\endgroup$ – robjohn Dec 27 '16 at 16:47
  • $\begingroup$ Although I am not downvoter, if $n\equiv 11 \pmod {100}$, n could not be even. $\endgroup$ – Takahiro Waki Jan 15 '17 at 13:15
  • $\begingroup$ @TakahiroWaki: this is part of what I said. $\endgroup$ – robjohn Jan 15 '17 at 18:05
1
$\begingroup$

Any odd square is congruent to 1 modulo 4 $ (2n+1)^2 = 4n^2+4n+1 = 4(n^2+n)+1 \cong 1 \bmod{4} $

But 11 is congruent to 3 modulo 4.

Just as well any positive integer ending with 11 is not a perfect square.

$\endgroup$
1
$\begingroup$

If you examine the sequence formed by the last 2 digits of a square of an integer, or equivalently, look at the sequence $n^2 \pmod{100}$, it is easy to show that a square of an integer can only end with one of the following pairs of digits: 00, 01, 21, 41, 61, 81, 04, 24, 44, 64, 84, 06, 16, 36, 56, 76, 96, 09, 29, 49, 69, 89 or 25.

Each number in your sequence ends with $..11$, hence none of them can be squares.

From the above observation, it is also clear that many other sequences can also never contain a square, for example:

22, 222, 2222, ...

14, 414, 1414, 41414, ...

One could spend many happy hours creating such sequences.

$\endgroup$
  • 2
    $\begingroup$ ``I have been designed by the Sirius Cybernetics Corporation to take you, the visitor to the Hitch Hiker's Guide to the Galaxy, into these their offices. If you enjoy your ride, which will be swift and pleasurable, then you may care to experience some of the other elevators which have recently been installed in the offices of the Galactic tax department, Boobiloo Baby Foods and the Sirian State Mental Hospital, where many ex-Sirius Cybernetics Corporation executives will be delighted to welcome your visits, sympathy, and happy tales of the outside world.'' $\endgroup$ – Will Jagy Jun 18 '13 at 22:46
  • 2
    $\begingroup$ $$\begin{array}{l}\text{Little Jack Horner}\cr \text{Sits in a corner}\cr \text{Extracting cube roots to infinity,}\cr \text{An assignment for boys}\cr \text{That will minimize noise}\cr \text{And produce a more peaceful vicinity.}\end{array}$$ $\endgroup$ – Will Jagy Jun 18 '13 at 23:15
1
$\begingroup$

Let's first reformulate the claim: $$ \nexists n \in \mathbb{Z}, k \in \{11, \space 111, \space \ldots \} : n^2 = k $$

Proof: First, consider all non-negative integers $n$ such that $n$ is even. That is, $$ n = 2j \space \space \forall j \in \mathbb{Z} $$ For these $n$ we know that $n^2$ is of the form: $$ n^2 = (2j)^2 = 2^2 \cdot j^2 = 4j^2 $$ This means $n^2$ can be divided by 2 at least twice. Another way of saying this is that half of $n^2$ is even. However, $k$ is of the following form: $$ k = 10a + 1 \space \space \forall a \in \{1, \space 11, \space \ldots \} $$ Since $10a$ is even, $10a + 1$ is not. However, since $n^2$ is divisible by 4, it is also even. Hence we know that: $$ \nexists n \in \mathbb{Z}, j \in \mathbb{Z}, k \in \{11, \space 111, \space \ldots \} : n = 2j \space \land \space n^2 = k $$ That leaves us with all non-negative integers $n$ such that $n$ is uneven. Those can be written as: $$ n = 2j + 1 \space \space \forall j \in \mathbb{Z} $$ In this case $n^2$ will have the form: $$ n^2 = (2j + 1)^2 = 4j^2 + 4j + 1 $$ We can see right away that this number is odd. But $k$ is odd too, so that is of no help. However, the other terms of $n^2$ all contain a factor of 4. That means $n^2 - 1$ is divisible by 4. Since that is even stronger than knowing a number is even, we should compare $n^2 - 1$ to $k - 1$ and see if $k - 1$ fits the same bill. Let's re-write this argument in Mathese and see if $k - 1$ is divisible by 4: $$ n^2 = k \iff n^2 - 1 = k - 1 $$ $$ n^2 - 1 = 4j^2 + 4j = 4(j + 1) \implies 4 \space | \space n^2 - 1 $$ Hence $n^2 = k \iff 4 \space | \space k - 1$. Let's try to reformulate $k$ in such a way that shows whether $k$ is divisible by 4:

$$ k \in \{11, \space 111, \space \ldots \} \iff k - 1 \in \{ 11 - 1, \space 111 - 1, \space \ldots \} $$ $$ \kern 47pt \iff k - 1 \in \{ 10, \space 110, \space \ldots \} $$ $$ \kern 73pt \iff k - 1 \in \{ 10 \cdot 1, \space 10 \cdot 11, \space \ldots \} $$ Since $10$ is even but not divisible by 4, the other factor that composes $k - 1$ must be even for $k - 1$ to be divisible by 4 as well. We can write an equation that separates the factor $10$ from the factor that is an element of $\{1, \space 11, \space \ldots \}$. $$ k - 1 = 10 \cdot j \space \forall j \in \{1, \space 11, \space \ldots \} $$ Since we know already that $\{11, \space 111, \space \ldots \}$ contains only uneven numbers and $1$ is uneven, we know the set $\{1\} \cup \{11, \space 111, \space \ldots \} \equiv \{1, \space 11, \space \ldots \}$ contains only uneven numbers as well.

Hence $4 \nmid k - 1 \space \forall k \in \{11, \space 111, \space \ldots \}$.

Hence $ \nexists n \in \mathbb{Z}, k \in \{11, \space 111, \space \ldots \} : n^2 = k $

Which is that what was to be proven.

$\endgroup$
1
$\begingroup$

Well, consider an odd number $n = 2k + 1$. Then, $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1$.

So, $n^2 \equiv 1 \pmod{4}$, or, in other words, $n^2$ will always give you a remainder of 1 on division by 4 if n is odd.

On the other hand, if n is even, then, say, $n = 2k \Longrightarrow n^2 = 4k^2 \Longrightarrow n^2 \equiv 0 \pmod{4}$. Or, $n^2$ gives you a remainder of 0 on division by 4.

So for any integer $n$, we know that $n^2 \equiv 0 \pmod{4}$ if n is even and $n^2 \equiv 1 \pmod{4}$ if n is odd.

Now, let's look at the numbers in the given sequence. Firstly, note that 100 is divisible by 4. And, say, split each number into a multiple of 100 added to 11.

For example, $1111 = 1100 + 11, 11111 = 11100 + 11, \cdots$.

Now, each number in the sequence is equivalent to $11 \pmod{4}$. But $11 \equiv 3 \pmod{4}$, so each number in the sequence gives a remainder of 3 on division by 4.

But this is impossible for a square number, as we've shown above.

Therefore, no number in this sequence is a square. Q.E.D.

$\endgroup$
0
$\begingroup$

We can do it in a easier method. See that a square is the former of 4k & 8k+1 But in the sequence it is clear that 11,111,1111 .....is not divided by 4. We also can not represent it with 4k+1 because 11-1,111-1.....or 10,110,1110 should be divided by 4. We know that a number is divided by 4 if the sum of the last 2 digital is divided by 4.So it is clear that 10, 110,1110 is not divided by. Hence it is proved.

$\endgroup$
  • $\begingroup$ This is the same answer as the one provided by the user celtschk four and a half years ago. $\endgroup$ – José Carlos Santos Jan 21 '18 at 13:39

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.