- #1

- 248

- 0

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter bonfire09
- Start date

- #1

- 248

- 0

- #2

- 795

- 7

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?

- #3

- 1,225

- 75

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.

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:

- #4

- 248

- 0

- #5

- 248

- 0

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.

- #6

- 795

- 7

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 dont 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.

- #7

mathwonk

Science Advisor

Homework Helper

2020 Award

- 11,136

- 1,329

your predicament suggests that you lack the basic idea. hopefully it is getting clearer with this example.

- #8

- 248

- 0

- #9

- 841

- 0

I don't see the work where you showed or gave an explanation why it repeats for 4,5,6?

- #10

- 33

- 0

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

- 841

- 0

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.

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)

- #12

- 33

- 0

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}

- #13

- 841

- 0

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.

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.

- #14

- 248

- 0

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.

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

- 795

- 7

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

- 248

- 0

Where m is an integer.

- #17

- 841

- 0

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?

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.

- #18

- 841

- 0

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.

Where m is an integer.

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:

Share: