let a be a solution of x^2\equiv 1 (mod m). Show that m-a is also a solution.

dwsmith

MHF Hall of Honor
Mar 2010
3,093
582
Florida
let \(\displaystyle a\) be a solution of \(\displaystyle x^2\equiv 1 \ \mbox{(mod m)}\). Show that \(\displaystyle m-a\) is also a solution.

\(\displaystyle a^2\equiv 1 \ \mbox{(mod m)}\)

\(\displaystyle (m-a)^2\equiv 1 \ \mbox{(mod m)}\rightarrow m^2-2am+a^2\equiv 1 \ \mbox{(mod m)}\rightarrow m^2-2am+1\equiv 1 \ \mbox{(mod m)}\)

\(\displaystyle \rightarrow m-2a\equiv 0 \ \mbox{(mod 1)}\)

Not sure if this is going anywhere.
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
let \(\displaystyle a\) be a solution of \(\displaystyle x^2\equiv 1 \ \mbox{(mod m)}\). Show that \(\displaystyle m-a\) is also a solution.

\(\displaystyle a^2\equiv 1 \ \mbox{(mod m)}\)

\(\displaystyle (m-a)^2\equiv 1 \ \mbox{(mod m)}\rightarrow m^2-2am+a^2\equiv 1 \ \mbox{(mod m)}\rightarrow m^2-2am+1\equiv 1 \ \mbox{(mod m)}\)

\(\displaystyle \rightarrow m-2a\equiv 0 \ \mbox{(mod 1)}\)

Not sure if this is going anywhere.
m-a is congruent to -a (mod m). Square this and you get a^2.
 

[email protected]

MHF Hall of Honor
Sep 2008
1,163
429
Champaign, Illinois
let \(\displaystyle a\) be a solution of \(\displaystyle x^2\equiv 1 \ \mbox{(mod m)}\). Show that \(\displaystyle m-a\) is also a solution.

\(\displaystyle a^2\equiv 1 \ \mbox{(mod m)}\)

\(\displaystyle (m-a)^2\equiv 1 \ \mbox{(mod m)}\rightarrow m^2-2am+a^2\equiv 1 \ \mbox{(mod m)}\rightarrow m^2-2am+1\equiv 1 \ \mbox{(mod m)}\)

\(\displaystyle \rightarrow m-2a\equiv 0 \ \mbox{(mod 1)}\)

Not sure if this is going anywhere.
I prefer undefined's method more, but if you want to solve this the way you were, then \(\displaystyle (m-a)^2=m^2-2am+a^2\equiv a^2\bmod{m} \)

Now, we know what \(\displaystyle a^2 \) is equivalent to modulo \(\displaystyle m \) (Wink).