My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum

Reply
 
LinkBack Thread Tools Display Modes
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
munchiez is offline  
 
April 23rd, 2012, 04:42 AM   #2
Math Team
 
mathbalarka's Avatar
 
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
mathbalarka is online now  
April 23rd, 2012, 04:51 AM   #3
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 12,859
Thanks: 94

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.
CRGreathouse is offline  
April 23rd, 2012, 04:55 AM   #4
Math Team
 
mathbalarka's Avatar
 
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?
mathbalarka is online now  
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
munchiez is offline  
April 23rd, 2012, 05:41 AM   #6
Math Team
 
mathbalarka's Avatar
 
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
mathbalarka is online now  
April 23rd, 2012, 05:52 AM   #7
Global Moderator
 
The Chaz's Avatar
 
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
The Chaz is offline  
April 23rd, 2012, 06:01 AM   #8
Math Team
 
mathbalarka's Avatar
 
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
mathbalarka is online now  
April 23rd, 2012, 06:16 AM   #9
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 12,859
Thanks: 94

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 when you don't have access to special characters.
CRGreathouse is offline  
April 23rd, 2012, 06:23 AM   #10
Math Team
 
mathbalarka's Avatar
 
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?
mathbalarka is online now  
April 23rd, 2012, 06:29 AM   #11
Math Team
 
mathbalarka's Avatar
 
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
mathbalarka is online now  
April 23rd, 2012, 06:41 AM   #12
Global Moderator
 
The Chaz's Avatar
 
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 when you don't have access to special characters.
... or when you're too lazy for LaTex
The Chaz is offline  
April 23rd, 2012, 06:49 AM   #13
Math Team
 
mathbalarka's Avatar
 
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 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!
mathbalarka is online now  
April 23rd, 2012, 07:02 AM   #14
Global Moderator
 
The Chaz's Avatar
 
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)
The Chaz is offline  
April 23rd, 2012, 07:14 AM   #15
Math Team
 
mathbalarka's Avatar
 
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
mathbalarka is online now  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
abmod, prove


Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
prove 7>(2^0.5+5^0.5+11^0.5) Albert.Teng Algebra 8 February 7th, 2013 09:14 PM
Goldbach's conjecture (to prove or not to prove) octaveous Number Theory 13 September 23rd, 2010 04:36 AM
prove: rose3 Number Theory 1 February 16th, 2010 10:23 AM
prove prove prove. currently dont know where to post qweiop90 Algebra 1 July 31st, 2008 06:27 AM
prove prove prove. currently dont know where to post qweiop90 New Users 1 January 1st, 1970 12:00 AM





Copyright © 2014 My Math Forum. All rights reserved.