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

  • Thread starter privyet
  • Start date
In summary, if a and b are integers and a\equivb(mod n), then a2\equivb2(mod n). If n divides a-b, then n also divides a2-b2.
  • #1
privyet
13
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[itex]\equiv[/itex]b(mod n), then a2[itex]\equiv[/itex]b2(mod n).

The Attempt at a Solution



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

Any help much appreciated.
 
Last edited:
Physics news on Phys.org
  • #2
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[itex]\equiv[/itex]b(mod n), then a2[itex]\equiv[/itex]b2(mod n).

The Attempt at a Solution



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

In other words, n divides a-b. Does n divide a2-b2?
 
  • #3
Yeah. I know its simple but I just don't know how to think about it.
 
  • #4
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?
 
  • #5
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 ?
 
  • #6
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[itex]\equiv[/itex]b2(mod n).

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

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

What does it mean for a and b to be congruent modulo n?

Two numbers a and b are said to be congruent modulo n if they have the same remainder when divided by n. This is denoted as a ≡ b (mod n).

What is the significance of proving a=b(mod n) implies a^2=b^2(mod n)?

This proof is important because it demonstrates that the congruence relation is preserved under squaring. In other words, if two numbers are congruent modulo n, then their squares will also be congruent modulo n.

What is the general approach to proving a congruence relation such as a=b(mod n)?

The general approach is to show that a and b have the same remainder when divided by n. This can be done by using the division algorithm to express a and b in terms of n, and then comparing their remainders.

Can this statement be generalized to higher powers, such as a^n=b^n(mod n)?

Yes, this statement can be generalized to any positive integer power. In other words, if a and b are congruent modulo n, then a^n and b^n will also be congruent modulo n.

What are some real-world applications of this congruence relation?

This congruence relation is used in various areas of mathematics such as number theory, cryptography, and algebra. It also has applications in computer science, particularly in the design of efficient algorithms for computations involving large numbers.

Similar threads

Show that ## a^2\equiv b^2 \mod n ## need not imply that ## a\equiv b \mod n ##
    • Precalculus Mathematics Homework Help
Replies
10
Views
2K
Prove ## a/d\equiv b/d \mod n/d ##.
    • Precalculus Mathematics Homework Help
Replies
2
Views
716
Prove that ## a^{({2}^{n})}\equiv 1\pmod {2^{n+2}} ## for any ##n##?
    • Precalculus Mathematics Homework Help
Replies
6
Views
1K
Modular Equation Solving | x2 + 8x ≡ 0 (mod 56) | Step-by-Step Guide
    • Precalculus Mathematics Homework Help
Replies
1
Views
902
Prove that ## b\equiv c\pmod {n} ##, where the integer is....
    • Precalculus Mathematics Homework Help
Replies
1
Views
768
Prove that if n^2 is a multiple of 2, then n is multiple of 2
    • Precalculus Mathematics Homework Help
Replies
23
Views
3K
Prove that ## n ## must be a power of ## 2 ##
    • Precalculus Mathematics Homework Help
Replies
15
Views
987
I Question on Primitive Roots and GCDs
    • Linear and Abstract Algebra
Replies
2
Views
840
Prove that if ## n>2 ##, then there exists a prime ## p ## satisfying....
    • Precalculus Mathematics Homework Help
Replies
8
Views
2K
Prove that if a & b are odd then a+b is even
    • Precalculus Mathematics Homework Help
Replies
4
Views
4K

Hot Threads

Recent Insights

Back
Top