Proving the Congruence of n^2 Mod 7: A Modular Problem in Number Theory

  • Context: Undergrad 
  • Thread starter Thread starter bonfire09
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around proving that for every integer n, n^2 is congruent to exactly one of the values 0, 2, or 4 modulo 7. Participants explore various approaches to the problem, including specific cases and modular arithmetic principles.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants suggest testing only n = 0, 1, 2, and 3 to simplify the proof, as higher values will repeat due to modular properties.
  • One participant explains that integers can be expressed in the form 7m + k, where k ranges from 0 to 6, and that squaring these forms leads to congruences that can be reduced.
  • Another participant points out that certain values, like 4 and 6, can be omitted from testing because they are congruent to other values when squared.
  • Some participants provide specific calculations for n^2 mod 7 for n = 0, 1, 2, and 3, showing the results and discussing their implications.
  • There is a correction regarding the interpretation of the original problem statement, with some participants clarifying that 1^2 is not included in the set {0, 2, 4} mod 7.
  • One participant emphasizes the importance of a complete proof, suggesting that all cases should be addressed to avoid overlooking any potential values.
  • Another participant raises a question about how the proof addresses cases where n = 7m + 4, 5, or 6, indicating a need for further clarification on these scenarios.

Areas of Agreement / Disagreement

Participants express differing views on which cases need to be tested and how to interpret the problem statement. There is no consensus on the necessity of including all potential cases in the proof, and some participants challenge the completeness of others' arguments.

Contextual Notes

Some participants note that the proof's completeness may depend on the level of rigor expected in the class, suggesting that introductory courses might require more thorough explanations.

bonfire09
Messages
247
Reaction score
0
I have to prove "For every integer n, n^2 is congruent to exactly one 0,2,or 4mod 7? I don't even know where to start? Apparently its a problem that has 6 other problems to it too meaning a-f and my professor assigned us the last one.
 
Physics news on Phys.org
bonfire09 said:
I have to prove "For every integer n, n^2 is congruent to exactly one 0,2,or 4mod 7? I don't even know where to start? Apparently its a problem that has 6 other problems to it too meaning a-f and my professor assigned us the last one.

Hint: You don't have to do it for every n; just for n = 0, 1, 2, 3, 4, 5, 6. Why? And if you think about it a little, you really only need to test n = 0, 1, 2, and 3. Why?
 
Hi
Any integer is written as 7m+k where k=0,1,2,3,4,5,6. mod((7m+k)^2) = mod(k^2) for modulus 7.
You can get possible cases in seven calculations. As SteveL27 says you can reduce number of calculations half with attention that mod((7m+k)^2)=mod((7m-k)^2)=mod({7(m-1)+(7-k)}^2)=mod((7-k)^2)=mod(k^2)

In similar ways
For modulus 2, Ans {0,1}
For modulus 3, Ans {0,1}
For modulus 4, Ans {0,1}
For modulus 5, Ans {0,1,4}
For modulus 6, Ans {0,1,3,4}
For modulus 7, Ans {0,1,2,4}
For modulus 8, Ans {0,1,2,3,4}
For modulus 10, Ans {0,1,4,5,6,9}

Regards.
 
Last edited:
thanks for the explanation! I think I get what you guys say. I'm going to figure it out and see how far I can get.
 
Hint: You don't have to do it for every n; just for n = 0, 1, 2, 3, 4, 5, 6. Why? And if you think about it a little, you really only need to test n = 0, 1, 2, and 3. Why?

Oh that's because 4 and 6 are multiples of 2 and 3 and 5 is basically 2(2)+1.
 
bonfire09 said:
Oh that's because 4 and 6 are multiples of 2 and 3 and 5 is basically 2(2)+1.

What I had in mind was that 4 = -3 (mod 7) so you don't have to test 4 since you're squaring.

4^2 is already the same as (-3)^2 = 3^2. So you only need to check 3 but not 4. Likewise you don't have to check 5 or 6.
 
the whole point of modular arithmetic is that every specific problem can be done in a finite amount of time by anyone no matter how clueless, just by trying all the cases.

your predicament suggests that you lack the basic idea. hopefully it is getting clearer with this example.
 
I proved it by using 4 cases where n=0,n=1,n=2, and n=3. And showed that each case was congruent to exactly one thing. As you use 4,5,6... it repeats so I chose not to show those in my proof.
 
bonfire09 said:
I proved it by using 4 cases where n=0,n=1,n=2, and n=3. And showed that each case was congruent to exactly one thing. As you use 4,5,6... it repeats so I chose not to show those in my proof.
I don't see the work where you showed or gave an explanation why it repeats for 4,5,6?
 
  • #10
@bonfire09:
Depending on the situation, you may want to show that the cases repeat. For example, showing these 3 computations should be satisfactory (though if this is for an introductory class, it might be prudent to be more rigorous than this):

0^2 mod 7 = 0
1^2 mod 7 = 1 = 6^2 mod 7
2^2 mod 7 = 4 = 5^2 mod 7
3^2 mod 7 = 2 = 4^2 mod 7

Also, in response to your very first post, 1^2 is not in {0,2,4} mod 7 :P

(I think you made a typo)
 
  • #11
Eval said:
@bonfire09:
Depending on the situation, you may want to show that the cases repeat. For example, showing these 3 computations should be satisfactory (though if this is for an introductory class, it might be prudent to be more rigorous than this):

0^2 mod 7 = 0
1^2 mod 7 = 1 = 6^2 mod 7
2^2 mod 7 = 4 = 5^2 mod 7
3^2 mod 7 = 2 = 4^2 mod 7

Also, in response to your very first post, 1^2 is not in {0,2,4} mod 7 :P

(I think you made a typo)
No, Bonfire wrote 0, 1, 4, 2 as "one, 0, 4, 2". In my post, I tried to say that any proof must be complete,i.e. you can't merely ignore the 4,5,6.
 
  • #12
I know, that was what I was saying. I was responding to him, not you, sorry :/

Also, I read that as a different syntax. I thought he was saying "congruent to exactly one 0,2,or 4mod 7" meaning that it was one of the values in the list {0,2,4}

EDIT: This is one of those cases where you could get away with "WLOG" (Without Loss of Generality), depending on the level at which you are writing the proof.
 
  • #13
Eval said:
I know, that was what I was saying. I was responding to him, not you, sorry :/

Also, I read that as a different syntax. I thought he was saying "congruent to exactly one 0,2,or 4mod 7" meaning that it was one of the values in the list {0,2,4}

EDIT: This is one of those cases where you could get away with "WLOG" (Without Loss of Generality), depending on the level at which you are writing the proof.
Yeah, it could be read either way, which is how some professors try to confuse things to make the student think. As for your edit, I disagree.
 
  • #14
Oh yeah here is my proof:
Case:1 let n=0
Since n=0 then n^2=0. Hence 0 is congruent to 0mod 7.
Case 2:let n=1
Since n=1 then n^2=1. Hence 1 is congruent to 1mod7.
Case 3 let n=2
Since n=2 then n^2=4. Hence 4 is congruent to 4mod7.
Case 4 let n=3
Since n=3 then n^2=9. Hence 9 is congruent to 2mod7.
This is the rundown of my proof. There is not much to assume here except that n is an integer. And prove that each integer n^2 is congruent to exactly one of the four cases.
 
Last edited:
  • #15
bonfire09 said:
Oh yeah here is my proof:
Case:1 let n=0
Since n=0 then n^2=0. Hence 0 is congruent to 0mod 7.
Case 2:let n=1
Since n=1 then n^2=1. Hence 1 is congruent to 1mod7.
Case 3 let n=2
Since n=2 then n^2=4. Hence 4 is congruent to 4mod7.
Case 4 let n=3
Since n=3 then n^2=9. Hence 9 is congruent to 2mod7.
This is the rundown of my proof. There is not much to assume here except that n is an integer. And prove that each integer n^2 is congruent to exactly one of the four cases.

What happens if n = 5793459834895479437?
 
  • #16
Dang! Oh i forgot to represent the integer n as an arbitrary value meaning that n=7m, 7m+1,7m+2,etc
Where m is an integer.
 
  • #17
bonfire09 said:
Oh yeah here is my proof:
Case:1 let n=0
Since n=0 then n^2=0. Hence 0 is congruent to 0mod 7.
Case 2:let n=1
Since n=1 then n^2=1. Hence 1 is congruent to 1mod7.
Case 3 let n=2
Since n=2 then n^2=4. Hence 4 is congruent to 4mod7.
Case 4 let n=3
Since n=3 then n^2=9. Hence 9 is congruent to 2mod7.
This is the rundown of my proof. There is not much to assume here except that n is an integer. And prove that each integer n^2 is congruent to exactly one of the four cases.
How does your proof address the question of whether n = 7m + 4 , 7m +5 and 7m +6 give one of the same values for n = 0 to 3?
 
  • #18
bonfire09 said:
Dang! Oh i forgot to represent the integer n as an arbitrary value meaning that n=7m, 7m+1,7m+2,etc
Where m is an integer.
But the 4 cases you gave even if taken mod 7 do not address the case mentioned by SteveL27 since that is the case where n = 7m + 5, which is not one of the four cases you did.

Actually you could had broken it down into one of the following 4 cases:

n = 7m
n = 7m +/- 1
n = 7m +/- 2
n = 7m +/- 3
 
Last edited:

Similar threads

Undergrad Congruence Subgroups and Modular Forms Concept Questions
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Congruence of all integers n, 4^n and 1 +3n mod(9)?
  • · Replies 3 ·
Replies
3
Views
5K
Graduate About a natural extension of Collatz conjecture
  • · Replies 3 ·
Replies
3
Views
901
Undergrad Congruence Question: Proving m=n (mod p-1)
  • · Replies 3 ·
Replies
3
Views
3K
Graduate Number of quadratic residues mod N>1
  • · Replies 3 ·
Replies
3
Views
4K
Graduate Brocard's Problem: No Solution for n! Containing Prime^2, n>7?
  • · Replies 3 ·
Replies
3
Views
5K
Finding the orders of 1, 2, .... , 16 (mod 17)
  • · Replies 1 ·
Replies
1
Views
6K
Graduate Divisibility and Congruence problem
  • · Replies 3 ·
Replies
3
Views
4K
Graduate Conjecture: There exists no number k s.t. k^2+2 is a multiple of 7
  • · Replies 5 ·
Replies
5
Views
3K
Graduate How to Prove the Sum of \(1^k + 2^k + ... + (p-1)^k \mod p\)?
  • · Replies 9 ·
Replies
9
Views
5K