Suppose that n=x2 is a perfect square with an even number of base-10 digits. Assume that when n is written backwards, you get another perfect square y2. Prove that 121|n. (Use the mod 11 divisibility test, and the fact that -1 is a quadratic non-residue mod 11.)
I know by using the mod 11 divisibility test (where you add and subtract alternating digits) that x2≡−y2 (mod 11). I believe, also, that since x2 is a quadratic residue mod 11 and −y2 is a quadratic non-residue mod 11, by the properties of Legendre symbols it can't be true that gcd(x2,11)=gcd(y2,11)=1, so 11 divides x2 and y2. But after that, I'm stuck, and I don't know how to get to the conclusion that 121|n. Help, please?
Answer
as you said, It is easy to see that if n has an even number of digits then the number obtained when reversing the digits is congruent to −nmod11.
Therefore n and −n are quadratic residues. Suppose n is not 0mod11. Now use the fact the quadratic residues form a subgroup of the multiplicative group Z∗11. So n−1 is a quadratic residue, and subsequently n−1(−n)≡−1 is a quadratic residue mod11. This is a contradiction, the quadratic residues mod11 are 0,1,4,9,5,3.
We conclude n≡0mod11. So 11|n, and since n is a square 112|n (since 11 is a prime).
No comments:
Post a Comment