Arts & Humanities
Beauty & Style
Business & Finance
Cars & Transportation
Computers & Internet
Consumer Electronics
Dining Out
Education & Reference
Entertainment & Music
Environment
Family & Relationships
Food & Drink
Games & Recreation
Health
Home & Garden
Local Businesses
News & Events
Pets
Politics & Government
Pregnancy & Parenting
Science & Mathematics
Social Science
Society & Culture
Sports
Travel
Yahoo Products

15 years ago

here's the whole problem please help!!!!
a) Prove or disprove: If a^2 is congruent to b^2(mod n), the a is congruent to b(mod n) or a is congruent to -b(mod n)
b) Do part (a) when n is prime

Top 1 Answers

15 years ago

Favorite Answer
Statement a is not true. For a counterexample:
1² (mod 6) = 1 and 5² (mod 6) = 1. However, 1 (mod 6) = 1 and 5 (mod 6) = 5.
Statement b is true. Here is the proof:
Given a² (mod p) = b² (mod p) for p prime. Then:
a² (mod p) - b² (mod p) = 0
(a² - b²)(mod p) = 0
((a+b)(a - b))(mod p) = 0
Therefore, p is divisible by (a+b)(a-b). Since p is prime, p must be divisible by either (a+b) or (a-b). That leaves two possibilities:
• If p = a + b, then a (mod p) = b (mod p).
• If p = a - b, then a (mod p) = -b (mod p).
That completes the proof.
* * * * *
Oops, maybe b isn't true after all. For example, 3² (mod 7) = 2 and 4² (mod 7) = 2. However, 3 (mod 7) ≠ 4 (mod 7). I think this will be true whenever a + b = p.

1

Is she really my "Best Friend" like she says?If you chose to name your kids after famous characters on TV shows, who would they be?why do uracil is replaced by thymine in RNA?A couple of the other questions. I'd really appreciate the advice.?how often should i feed my medium sized dog? and why did he growl and stand up in the middle of my sleep?Can a computer's BIOS Software be infected?My Hamster Died?!!?Why can't I make headway with my fixed-rate mortgage?Telling him the truth a year later?Kitten with scabies?