Tuesday, 12 November 2019

elementary number theory - Prove that a perfect square (also a perfect square backwards) is divisible by 121



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 x2y2 (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 Z11. So n1 is a quadratic residue, and subsequently n1(n)1 is a quadratic residue mod11. This is a contradiction, the quadratic residues mod11 are 0,1,4,9,5,3.



We conclude n0mod11. So 11|n, and since n is a square 112|n (since 11 is a prime).


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...