Divisibility (1 Viewer)

[HeroicPandas]

I'm going to prove this, omitting lots of words and formality

If 7|x^2 + y^2, then there exists a positive integer M such that





Since M in an integer, then x^2/7 and y^2/7 must also be integers

So 7|x^2 and 7|y^2

Thus 7|x and 7|y

and then we prove the converse, if 7|x and 7|y, then 7|x^2 + y^2 (not the problem I have)

So is my proof correct?

Is the blue correct? (i.e. is there enough reasoning to deduce that 7|x^2 and 7|y^2?)


Thanks

 

[Sy123]

The first blue line is incorrect, for example,

1.5 + 2.5 = 4,

4 is an integer, but the sum of 2 numbers being an integer does not mean those numbers are integers.

This is just a guess, but I believe you will need to use the fact that 7 is prime. Otherwise your argument can be generalized to any integer n since your method is not specific to the number 7.

 

[HeroicPandas]

The first blue line is incorrect, for example,

1.5 + 2.5 = 4,

4 is an integer, but the sum of 2 numbers being an integer does not mean those numbers are integers.

This is just a guess, but I believe you will need to use the fact that 7 is prime. Otherwise your argument can be generalized to any integer n since your method is not specific to the number 7.

Ahhhh, ok thanks

I'll come back when an idea sparks

 

[seanieg89]

Do you know what quadratic residues are?

 

[HeroicPandas]

Do you know what quadratic residues are?

No idea, but I just had a quick google and saw the words 'congruent modulo'. Now I know where I'm heading (time to use some modulo)

 

[anomalousdecay]

No idea, but I just had a quick google and saw the words 'congruent modulo'. Now I know where I'm heading (time to use some modulo)

We briefly skipped over modulo in lectures though.

Luckily I know how to convert bases, but still a majority of people would have been like "what?" when we were shown the field of integers 5.

 

[seanieg89]

Quadratic residues (modulo n) are just what squares can be modulo n.

Eg. In this case (mod 7) we have

0^2=0
1^2=1
2^2=4
3^2=2
4^2=(-3)^2=2
5^2=(-2)^2=4
6^2=(-1)^2=1

(note the mirrored pattern due to the negatives, this will save you time in future questions.)

So the quadratic residues (mod 7) are 0,1,2,4 mod 7.

Saying that x^2+y^2=0 mod 7 is saying that two residues sum to 0 mod 7. But my inspection, the only pair of the above residues that sum to 0 are 0 and 0.

And the only way 0 came about as a residue was from squaring 0.

So we must have x=y=0 mod 7, as required.

 

[HeroicPandas]

Quadratic residues (modulo n) are just what squares can be modulo n.

Eg. In this case (mod 7) we have

0^2=0
1^2=1
2^2=4
3^2=2
4^2=(-3)^2=2
5^2=(-2)^2=4
6^2=(-1)^2=1

(note the mirrored pattern due to the negatives, this will save you time in future questions.)

So the quadratic residues (mod 7) are 0,1,2,4 mod 7.

Saying that x^2+y^2=0 mod 7 is saying that two residues sum to 0 mod 7. But my inspection, the only pair of the above residues that sum to 0 are 0 and 0.

And the only way 0 came about as a residue was from squaring 0.

So we must have x=y=0 mod 7, as required.

Ahhhhhhhhh ok, thank you very much!

Yesterday I couldn't sleep because of this question, but I thought of one solution. I've read and understood your solution, but can you please check if my method is valid?

7|x^2 + y^2 is the same as saying

Which is the same as

Now we search for possible y-values by using the quadratic residue stuff and we find that the values of -y^2 are 0,1,2,4

-y^2 cannot equal to 1,2,4 because there is no solution for y (mod 7)

So -y^2 = 0, y^2 = 0

Now


So y^2 is divisible by 7 and hence y is divisible by 7

Do this similarly to x and we get the same result

EDIT 1: Bolded
EDIT 2: Quadratic residues (mod 7) are 1,2,4 and NOT 1,2,3,4

We briefly skipped over modulo in lectures though.

Luckily I know how to convert bases, but still a majority of people would have been like "what?" when we were shown the field of integers 5.

No worries because I learn this in discrete maths (modular arithmetic)

 

[Shadowdude]

Ahhhhhhhhh ok, thank you very much!

Yesterday I couldn't sleep because of this question, but I thought of one solution. I've read and understood your solution, but can you please check if my method is valid?

7|x^2 + y^2 is the same as saying

Which is the same as

Now we search for possible y-values by using the quadratic residue stuff and we find that the values of -y^2 are 0,1,2,3,4

-y^2 cannot equal to 1,2,3,4 because then y will be imaginary

So -y^2 = 0, y^2 = 0

Now


So y^2 is divisible by 7 and hence y is divisible by 7

Do this similarly to x and we get the same result



No worries because I learn this in discrete maths (modular arithmetic)

huh what

i think you mean "has no solution", or "this is impossible"


Your field has 7 elements: 0, 1, 2, 3, 4, 5 and 6. There's no imaginary numbers here.

 

[SpiralFlex]

I'll show when I get home a one line method

 

[Shadowdude]

I'll show when I get home a one line method

is it

7 | x^2 + y^2

so 7M = x^2 + y^2

but as 7 is prime, we know that x^2 + y^2 = 1 (with M = 7) or x^2 + y^2 = 7 (with M = 1) by unique prime factorisation

and then argue from there?

 

[HeroicPandas]

huh what

i think you mean "has no solution", or "this is impossible"


Your field has 7 elements: 0, 1, 2, 3, 4, 5 and 6. There's no imaginary numbers here.

Mmm yes

I'll show when I get home a one line method

:O

 

[SpiralFlex]

One direction: q -> p

Remember

It a|b and a|c does this imply a|sb+tc for integers s and t

Can you prove and use this?

 

[seanieg89]

Now we search for possible y-values by using the quadratic residue stuff and we find that the values of -y^2 are 0,1,2,3,4

-y^2 cannot equal to 1,2,3,4 because there is no solution

So -y^2 = 0, y^2 = 0

It's not clear to me what you are saying here...

 

[seanieg89]

but as 7 is prime, we know that x^2 + y^2 = 1 (with M = 7) or x^2 + y^2 = 7 (with M = 1) by unique prime factorisation

huh?

 

[Shadowdude]

oh wait sorry

x^2 + y^2 = 7M

means that

x^2 + y^2 = 7, M = 1

can't be other way around (as then 1 = 7)


(sorry, was in english mode)

 

[SpiralFlex]

Shadow I think you are confusing with what M is

 

[seanieg89]

oh wait sorry

x^2 + y^2 = 7M

means that

x^2 + y^2 = 7, M = 1

can't be other way around (as then 1 = 7)


(sorry, was in english mode)

Still nfi what you are trying to do. x^2 + y^2 can be any multiple of 7, it don't see why it suffices to consider M=1 or M=7.

 

[SpiralFlex]

M is any integer, cannot conclude M must be 1 or 7

 

[HeroicPandas]

It's not clear to me what you are saying here...

how about -y^2 cannot be equal to 1,2,4 because there is no solution for y (mod 7)?

(removed 3)