My Math Forum how to prove that if a=b(mod n) then ....

 Number Theory Number Theory Math Forum

 April 23rd, 2012, 04:31 AM #1 Joined: Apr 2012 Posts: 5 Thanks: 0 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
 April 23rd, 2012, 04:42 AM #2 Math Team     Joined: Mar 2012 From: India, West Bengal Posts: 3,815 Thanks: 42 Math Focus: Number Theory 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
April 23rd, 2012, 04:51 AM   #3
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 12,866
Thanks: 95

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

Quote:
 Originally Posted by mathbalarka 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.

April 23rd, 2012, 04:55 AM   #4
Math Team

Joined: Mar 2012
From: India, West Bengal

Posts: 3,815
Thanks: 42

Math Focus: Number Theory
Re: how to prove that if a=b(mod n) then ....

Yes, but what about my next solution,
Quote:
 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?

 April 23rd, 2012, 05:13 AM #5 Joined: Apr 2012 Posts: 5 Thanks: 0 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
 April 23rd, 2012, 05:41 AM #6 Math Team     Joined: Mar 2012 From: India, West Bengal Posts: 3,815 Thanks: 42 Math Focus: Number Theory 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
 April 23rd, 2012, 05:52 AM #7 Global Moderator     Joined: Nov 2009 From: Northwest Arkansas Posts: 2,766 Thanks: 2 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
April 23rd, 2012, 06:01 AM   #8
Math Team

Joined: Mar 2012
From: India, West Bengal

Posts: 3,815
Thanks: 42

Math Focus: Number Theory
Re: how to prove that if a=b(mod n) then ....

Quote:
 Originally Posted by The Chaz a == b

April 23rd, 2012, 06:16 AM   #9
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 12,866
Thanks: 95

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

Quote:
Originally Posted by mathbalarka
Quote:
 Originally Posted by The Chaz a == b
== is commonly used to mean $\equiv$ when you don't have access to special characters.

 April 23rd, 2012, 06:23 AM #10 Math Team     Joined: Mar 2012 From: India, West Bengal Posts: 3,815 Thanks: 42 Math Focus: Number Theory 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?
 April 23rd, 2012, 06:29 AM #11 Math Team     Joined: Mar 2012 From: India, West Bengal Posts: 3,815 Thanks: 42 Math Focus: Number Theory Re: how to prove that if a=b(mod n) then .... Ok, got it its a marvelous solution
April 23rd, 2012, 06:41 AM   #12
Global Moderator

Joined: Nov 2009
From: Northwest Arkansas

Posts: 2,766
Thanks: 2

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

Quote:
 Originally Posted by CRGreathouse ... == is commonly used to mean $\equiv$ when you don't have access to special characters.
... or when you're too lazy for LaTex

April 23rd, 2012, 06:49 AM   #13
Math Team

Joined: Mar 2012
From: India, West Bengal

Posts: 3,815
Thanks: 42

Math Focus: Number Theory
Re: how to prove that if a=b(mod n) then ....

Quote:
Originally Posted by The Chaz
Quote:
 Originally Posted by CRGreathouse ... == 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!

 April 23rd, 2012, 07:02 AM #14 Global Moderator     Joined: Nov 2009 From: Northwest Arkansas Posts: 2,766 Thanks: 2 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)
April 23rd, 2012, 07:14 AM   #15
Math Team

Joined: Mar 2012
From: India, West Bengal

Posts: 3,815
Thanks: 42

Math Focus: Number Theory
Re: how to prove that if a=b(mod n) then ....

Quote:
 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

 Tags abmod, prove

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Albert.Teng Algebra 8 February 7th, 2013 09:14 PM octaveous Number Theory 13 September 23rd, 2010 04:36 AM rose3 Number Theory 1 February 16th, 2010 10:23 AM qweiop90 Algebra 1 July 31st, 2008 06:27 AM qweiop90 New Users 1 January 1st, 1970 12:00 AM

 Contact - Home - Top