Prove if a=b(mod n) then a^2=b^2(mod n)

  • Thread starter Thread starter privyet
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on proving the mathematical statement that if \( a \equiv b \mod n \), then \( a^2 \equiv b^2 \mod n \) for integers \( a, b, n \) where \( n \geq 2 \). The proof involves recognizing that if \( n \) divides \( a - b \), it also divides \( a^2 - b^2 \) through the factorization \( a^2 - b^2 = (a + b)(a - b) \). The final proof demonstrates that \( a^2 \equiv b^2 \mod n \) holds true by expressing \( a^2 \) in terms of \( n \) and confirming the divisibility.

PREREQUISITES
  • Understanding of modular arithmetic
  • Familiarity with integer factorization
  • Basic knowledge of mathematical proofs
  • Ability to manipulate algebraic expressions
NEXT STEPS
  • Study the properties of modular arithmetic in detail
  • Learn about integer factorization techniques
  • Explore more complex proofs in 'Mathematical Proofs: A Transition to Advanced Mathematics'
  • Practice problems involving congruences and divisibility
USEFUL FOR

Students studying advanced mathematics, particularly those focusing on proofs and modular arithmetic, as well as educators looking for examples of mathematical reasoning.

privyet
Messages
12
Reaction score
1

Homework Statement



This is a question from the book I'm studying called 'Mathematical Proofs: A transition to advanced mathematics'

Homework Equations



Let a, b, n be integers, with n≥2. Prove that if a\equivb(mod n), then a2\equivb2(mod n).

The Attempt at a Solution



Following the examples I assumed that I'd start by stating that since a\equivb(mod n), then a-b=nx... but from this point I'm stuck.

Any help much appreciated.
 
Last edited:
Physics news on Phys.org
privyet said:

Homework Statement



This is a question from the book I'm studying called 'Mathematical Proofs: A transition to advanced mathematics'

Homework Equations



Let a, b, n be integers, with n≥2. Prove that if a\equivb(mod n), then a2\equivb2(mod n).

The Attempt at a Solution



Following the examples I assumed that I'd start by stating that since a\equivb(mod n), then a-b=nx...

In other words, n divides a-b. Does n divide a2-b2?
 
Yeah. I know its simple but I just don't know how to think about it.
 
privyet said:
Yeah. I know its simple but I just don't know how to think about it.

Are you saying you still don't know how to think about it after my hint? Can you answer my question in the hint?
 
privyet said:
Yeah. I know its simple but I just don't know how to think about it.
LCKurtz has probably provided the most direct way to think about it if you happen to know the well known factorization of the expression a2-b2, but alternatively you could think of it this way:

You have already stated that a-b=nx, or a=nx+b, for some integer x.

Can you find an integer, say y, such that a2=ny+b2 ?
 
I was saying that I could see that it looks pretty obvious that if n divides a-b, it will divide a2-b2, but that I didn't know how to prove it.

Using oay's hint about factorisation I've got a2-b2=(a+b)(a-b) and since n divides a-b, n therefore divides a2-b2 but this is looking very different to the examples in the book.

OK, after a pause to try again I think I've got it (with the help of oay's other hint):

Assume n divides a-b, then a=nx+b. Therefore a2=(nx+b)2=n2x2+2bnx+b2=n(nx2+2bx)+b2. Since a2=n(nx2+2bx)+b2 and nx2+2bx is an integer, a2-b2=n(nx2+2bx). Therefore a2\equivb2(mod n).

Is that right?
 
privyet said:
Is that right?
Spot on! :smile:
 
Great! Thank you both for your help.
 

Similar threads

Show that ## a^2\equiv b^2 \mod n ## need not imply that ## a\equiv b \mod n ##
  • · Replies 10 ·
Replies
10
Views
3K
Prove ## a/d\equiv b/d \mod n/d ##.
  • · Replies 2 ·
Replies
2
Views
1K
Modular Equation Solving | x2 + 8x ≡ 0 (mod 56) | Step-by-Step Guide
  • · Replies 1 ·
Replies
1
Views
1K
Prove that ## a^{({2}^{n})}\equiv 1\pmod {2^{n+2}} ## for any ##n##?
  • · Replies 6 ·
Replies
6
Views
3K
Prove that ##5 | (2^n a) \rightarrow (5 | a)##for any ##n##
  • · Replies 10 ·
Replies
10
Views
3K
Prove that if n^2 is a multiple of 2, then n is multiple of 2
  • · Replies 23 ·
Replies
23
Views
5K
Prove that ## b\equiv c\pmod {n} ##, where the integer is....
  • · Replies 1 ·
Replies
1
Views
1K
Prove that ## n ## must be a power of ## 2 ##
  • · Replies 15 ·
Replies
15
Views
2K
Modular Arithmetic proofs (multiplication and addition mod n)
  • · Replies 5 ·
Replies
5
Views
13K
Prove that if a & b are odd then a+b is even
  • · Replies 4 ·
Replies
4
Views
5K