I am trying to prove that $22^{1/2}$ is irrational using the classic proof by contradiction. I need to prove an auxiliary modular lemma:

if $n \not\equiv 0$ (mod 22) then $n^{2} \not\equiv 0$ (mod 22).

I know I can just list out all 21 cases where the remainder is a number 1 through 21, but could I just use a smaller mod? Such as mod 2, or mod 11 because they are factors of 22? And somehow relate that back to mod 22?

  • $\begingroup$ "I need to prove an auxiliary modular lemma." There are faster ways to prove it. Do you need a proof that uses this? $\endgroup$ – ajotatxe Feb 27 '17 at 19:23
  • $\begingroup$ @ajotatxe yes I have to use this $\endgroup$ – user7252850 Feb 27 '17 at 19:24
  • $\begingroup$ We can say $22$ divides $k$ if and only if $2$ divides $k$ and $k$ divides $k$. If you can prove that $2$ divides $n^2$ iff $2$ divides $n$, and the same for $11$, then you're good. $\endgroup$ – AJY Feb 27 '17 at 19:28
  • $\begingroup$ Do you already know that if a prime divides a product then it divides some factor of the product? $\endgroup$ – Bill Dubuque Feb 27 '17 at 22:03

Suppose $\;n^2=0\pmod{22}\;$ , then $\;n^2\;$ is even and divisible by $\;11\;$ , but then so is $\;n\;$ and there is the proof of your modular lemma (this is based on the fundamental theorem of arithmetic).

Now, suppose $\;\sqrt{22}=\frac mn\;$ , where $\;m,n\in\Bbb N\;,\;\;n\neq0\;$ is a reduced fraction , then:

$$22n^2\stackrel{(\color{red}*)}=m^2\overbrace{\implies}^{\text{the lemma}} m=0\pmod{22}\implies m=22 k\implies 22n^2\stackrel{(\color{red}*)}=22^2k^2\implies$$

$$n^2=22k^2\overbrace{\implies}^{\text{the lemma}} n=0\pmod{22}\;,\;\;\text{contradiction and we're done}$$


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.