Mod question

  • Thread starter TheMathNoob
  • Start date
In summary, congruence mod n means that two numbers have the same remainder when divided by n. In the case of n congruent to 6 mod 5, n is also congruent to 1 mod 5 because 5 divides n-6, and when divided by 5, the remainder is 1. However, in the case of 16 congruent to 2 mod 7, even though 7 divides 16-2, the remainder when dividing by 7 is not 2. Therefore, it is not necessary for b to be a perfect square in order for a^2 to be congruent to b mod n.
  • #1
189
4

Homework Statement


if n is congruent to 6 mod 5
then n is congruent to 1 mod 5?

Homework Equations




The Attempt at a Solution


[/B]
This is not a problem. It's a doubt that I have
 
Physics news on Phys.org
  • #2
TheMathNoob said:

Homework Statement


if n is congruent to 6 mod 5
then n is congruent to 1 mod 5?

Homework Equations




The Attempt at a Solution


[/B]
This is not a problem. It's a doubt that I have
Can you write 6 as congruent to x mod 5? What is x?
 
  • #3
ehild said:
Can you write 6 as congruent to x mod 5? What is x?
x is a number between 0 and 5
 
  • #4
What does it mean that a number n is congruent to x mod 5?
 
  • #5
ehild said:
What does it mean that a number n is congruent to x mod 5?
5 divides n-x
 
  • #6
TheMathNoob said:
5 divides n-x
Yes, but you said that x must be between 0 and 5. Which number is x if n=6?
 
  • #7
TheMathNoob said:
5 divides n-x
ehild said:
Yes, but you said that x must be between 0 and 5. Which number is x if n=6?
I got it by algebra 5 divides n-6 so n-6=5k, n=5(k+1)+1, so 5 divides n-1 which implies n is congruent to 1 mod 5. I am having another inquiry with my friend. He claims that 16 is not congruent to 2 mod 7 because he thinks that a^2 congruent to b mod n implies that b has to be a perfect square. Is that correct?
 
  • #8
TheMathNoob said:
I got it by algebra 5 divides n-6 so n-6=5k, n=5(k+1)+1, so 5 divides n-1 which implies n is congruent to 1 mod 5.
Correct.
TheMathNoob said:
I am having another inquiry with my friend. He claims that 16 is not congruent to 2 mod 7 because he thinks that a^2 congruent to b mod n implies that b has to be a perfect square. Is that correct?

a congruent to b mod n implies that a=kn+b. It follows that a2=(kn+b)2=k2n2+2knb+b2. If you divide that by n, the remainder is b2. But that remainder can be greater than n. It is the case with your example. 16 = 42, and 4 is 4 mod 7, so k=0, and b2=16. You have to do the division further to get 16 = 2*7+2. 16 is congruent to 2 mod 7.
 

Suggested for: Mod question

Replies
22
Views
1K
Replies
2
Views
528
Replies
12
Views
405
Replies
9
Views
429
Replies
8
Views
421
Replies
7
Views
438
Back
Top