## how to prove that if a=b(mod n) then ....

Math help on Congruences, Modulo, Fermat's Theorem, Fermat's Last Theorem (FLT), Euler's Theorem, Euler Totient Function, Divisors, Multiples, Prime Numbers, Prime Number Theorem, Distribution of Prime Numbers, Dzeta Function, Riemann Hypothesis, Algebraic Number Theory, Analytic Number Theory on My Math Forum.
Math problems in Number Theory

### how to prove that if a=b(mod n) then ....

hey i'm not really sure how i would go about writing out this answer..

"prove that if a = b (mod n) then a^2 = b^2 (mod n) "
as in if a and b are congruent to modulo n .. then a squared and b squared are congruent to modulo n ...

thanks munchiez
munchiez
Newcomer

Posts: 5
Joined: Mon Apr 23, 2012 7:22 am

### Re: how to prove that if a=b(mod n) then ....

By your problem, a isnt divisible by b.
let a^2 is divisible by b^2. Then (a/b)^2 = k where k is a integer. If k is a nonrootable number the we have nothing to do, it contradicts. If k is a rootable number, then a/b = p where p is an integer. By our primary assumption, it is impossible. So a^2 isnt divisible by b^2.
now by you assumption, a = b + nc where c is any integer. Then squaring both sides, it becomes
a^2 = b^2 + n(2bc + nc^2) so, a^2 = b^2 (mod n)
Q. E. D
Carl Friedrich Gauss —
When a philosopher says something that is true then it is trivial.
When he says something that is not trivial then it is false.

Pierre-Simon Laplace —
[said about Napier's logarithms:] ...by shortening the labours doubled the life of the astronomer.

Henri Poincaré —
Les faits ne parlent pas (Facts do not speak).

mathbalarka
Super User

Posts: 3461
Joined: Thu Mar 22, 2012 2:44 pm
Location: India, West Bengal

### Re: how to prove that if a=b(mod n) then ....

mathbalarka wrote:By your problem, a isnt divisible by b.

That doesn't follow. (a, b, n) = (2, 2, 2) is possible, and in that example a is divisible by b.
Pari/GP: this is the program I probably mentioned in my post. Windows users can get it at http://pari.math.u-bordeaux.fr/pub/pari ... -2-6-1.exe

CRGreathouse
Global Moderator

Posts: 12072
Joined: Sat Nov 25, 2006 9:52 am
Location: UTC -5

### Re: how to prove that if a=b(mod n) then ....

Yes, but what about my next solution,
now by you assumption, a = b + nc where c is any integer. Then squaring both sides, it becomes a^2 = b^2 + n(2bc + nc^2) so, a^2 = b^2 (mod n) Q. E. D

is it ok?
Carl Friedrich Gauss —
When a philosopher says something that is true then it is trivial.
When he says something that is not trivial then it is false.

Pierre-Simon Laplace —
[said about Napier's logarithms:] ...by shortening the labours doubled the life of the astronomer.

Henri Poincaré —
Les faits ne parlent pas (Facts do not speak).

mathbalarka
Super User

Posts: 3461
Joined: Thu Mar 22, 2012 2:44 pm
Location: India, West Bengal

### Re: how to prove that if a=b(mod n) then ....

hey thanks man, i guess my maths suck cause i dont quite get it, but i'll try get my head round it
munchiez
Newcomer

Posts: 5
Joined: Mon Apr 23, 2012 7:22 am

### Re: how to prove that if a=b(mod n) then ....

Ok, then let me try again, but this time i will try to be more descriptive,
a = b (mod n) means a - b is divisible by n
then a - b = n*c where c is an nonzero integer.
then a = b + n*c
Now squaring both sides , it becomes
a^2 = (b + n*c)^2
By the squaring formula,
a^2 = b^2 + 2b*n*c + (n^2)*(c^2) = b^2 + n*(2b*c + (c^2)*n)
We know that a,b,c,n are integers. So, 2b*c + (c^2)*n is an integer. It is also nonzero because c≠0.
then 2b*c + (c^2)*n = p where p is a non zero integer.
So, a^2 = b^2 + n*p = b^2 (mod n)
Q. E. D
Carl Friedrich Gauss —
When a philosopher says something that is true then it is trivial.
When he says something that is not trivial then it is false.

Pierre-Simon Laplace —
[said about Napier's logarithms:] ...by shortening the labours doubled the life of the astronomer.

Henri Poincaré —
Les faits ne parlent pas (Facts do not speak).

mathbalarka
Super User

Posts: 3461
Joined: Thu Mar 22, 2012 2:44 pm
Location: India, West Bengal

### Re: how to prove that if a=b(mod n) then ....

a == b
a - b == 0
(a - b)(a + b) == 0(a + b) == 0
(a^2 - b^2) == 0
a^2 == b^2

The Chaz
Global Moderator

Posts: 2766
Joined: Mon Nov 23, 2009 9:34 pm
Location: Northwest Arkansas

### Re: how to prove that if a=b(mod n) then ....

The Chaz wrote:a == b

Carl Friedrich Gauss —
When a philosopher says something that is true then it is trivial.
When he says something that is not trivial then it is false.

Pierre-Simon Laplace —
[said about Napier's logarithms:] ...by shortening the labours doubled the life of the astronomer.

Henri Poincaré —
Les faits ne parlent pas (Facts do not speak).

mathbalarka
Super User

Posts: 3461
Joined: Thu Mar 22, 2012 2:44 pm
Location: India, West Bengal

### Re: how to prove that if a=b(mod n) then ....

mathbalarka wrote:
The Chaz wrote:a == b

== is commonly used to mean $\equiv$ when you don't have access to special characters.
Pari/GP: this is the program I probably mentioned in my post. Windows users can get it at http://pari.math.u-bordeaux.fr/pub/pari ... -2-6-1.exe

CRGreathouse
Global Moderator

Posts: 12072
Joined: Sat Nov 25, 2006 9:52 am
Location: UTC -5

### Re: how to prove that if a=b(mod n) then ....

Didnt got it either, am i missing something? If a == b then how it is related to the original question?
Carl Friedrich Gauss —
When a philosopher says something that is true then it is trivial.
When he says something that is not trivial then it is false.

Pierre-Simon Laplace —
[said about Napier's logarithms:] ...by shortening the labours doubled the life of the astronomer.

Henri Poincaré —
Les faits ne parlent pas (Facts do not speak).

mathbalarka
Super User

Posts: 3461
Joined: Thu Mar 22, 2012 2:44 pm
Location: India, West Bengal

### Re: how to prove that if a=b(mod n) then ....

Ok, got it its a marvelous solution
Carl Friedrich Gauss —
When a philosopher says something that is true then it is trivial.
When he says something that is not trivial then it is false.

Pierre-Simon Laplace —
[said about Napier's logarithms:] ...by shortening the labours doubled the life of the astronomer.

Henri Poincaré —
Les faits ne parlent pas (Facts do not speak).

mathbalarka
Super User

Posts: 3461
Joined: Thu Mar 22, 2012 2:44 pm
Location: India, West Bengal

### Re: how to prove that if a=b(mod n) then ....

CRGreathouse wrote:...
== is commonly used to mean $\equiv$ when you don't have access to special characters.

... or when you're too lazy for LaTex

The Chaz
Global Moderator

Posts: 2766
Joined: Mon Nov 23, 2009 9:34 pm
Location: Northwest Arkansas

### Re: how to prove that if a=b(mod n) then ....

The Chaz wrote:
CRGreathouse wrote:...
== is commonly used to mean $\equiv$ when you don't have access to special characters.

... or when you're too lazy for LaTex

But to understand your method, someone needs a strong concept of congruence and its a bit tough to understand for newly NT readers on this forum!
Carl Friedrich Gauss —
When a philosopher says something that is true then it is trivial.
When he says something that is not trivial then it is false.

Pierre-Simon Laplace —
[said about Napier's logarithms:] ...by shortening the labours doubled the life of the astronomer.

Henri Poincaré —
Les faits ne parlent pas (Facts do not speak).

mathbalarka
Super User

Posts: 3461
Joined: Thu Mar 22, 2012 2:44 pm
Location: India, West Bengal

### Re: how to prove that if a=b(mod n) then ....

I don't think a *strong* understanding of modular arithmetic is necessary...
You just have to know that numbers are congruent means that their difference is (congruent to) zero. Using that 1 piece of information on the hypothesis and conclusion leads to

a - b == 0
Some step(s) in between...
a^2 - b^2 == 0

So there's only one step to take a - b to the difference of squares.
Is it really that hard to see? Maybe I'm just above average mathematical genius (American version).

(by the way, that "genius" comment is a joke about someone we used to know and love)

The Chaz
Global Moderator

Posts: 2766
Joined: Mon Nov 23, 2009 9:34 pm
Location: Northwest Arkansas

### Re: how to prove that if a=b(mod n) then ....

I don't think a *strong* understanding of modular arithmetic is necessary... You just have to know that numbers are congruent means that their difference is (congruent to) zero. Using that 1 piece of information on the hypothesis and conclusion leads to

a - b == 0 Some step(s) in between... a^2 - b^2 == 0

So there's only one step to take a - b to the difference of squares. Is it really that hard to see? Maybe I'm just above average mathematical genius (American version).

(by the way, that "genius" comment is a joke about someone we used to know and love)

Im not talking about me, im talking about the author of this topic, munchiez
Carl Friedrich Gauss —
When a philosopher says something that is true then it is trivial.
When he says something that is not trivial then it is false.

Pierre-Simon Laplace —
[said about Napier's logarithms:] ...by shortening the labours doubled the life of the astronomer.

Henri Poincaré —
Les faits ne parlent pas (Facts do not speak).

mathbalarka
Super User

Posts: 3461
Joined: Thu Mar 22, 2012 2:44 pm
Location: India, West Bengal

Next