Question

Is a^2 + b^2 coprime to a and b, if a and b are coprime between each other?

Answer 1

Hi

Answer 2

Hello there, @geneshie8

Answer 3

Still struggling quite hard with coprimes :/

Answer 4

Let's try proof by contradiction

Answer 5

Suppose p is a prime factor that divides both a and a^2 + b^2

Answer 6

Then there exist integers a' and c' that satisfy

a = pa'
a^2 + b^2 = pc'

Answer 7

With me so far ?

Answer 8

hi everybody ! @ganeshie8 i think from my past 4 years experience from here and different math. forums so i saw that peopels dont like - or dont know it how - working with proof by contradiction method - i dont know it way bc. this is easy - my opinion

Answer 9

sorry - i dont know it why ?

Answer 10

Yeah I see contradiction proofs very rarely here. But I do know a few ppl here who love contradiction so much that they always try it as their first attempt. I'm one of them haha

Answer 11

That was much shorter than my way, I am not even sure my way works 100% there are a few details wrong I think with my path.

Answer 12

Let's see here, we know from the problem that \(\gcd(a,b)=1\) and we want to see if these statements are true or not, \(\gcd(a^2+b^2,a)=1\) and \(\gcd(a^2+b^2,b)=1\).

I decided to just pick one and go with it.

\[\gcd(a^2+b^2,a)=\gcd(a^2-2ab+b^2,a)\]

So like you told us the other day, kY-kX = k(Y-X). We could repeat this multiple times though, kY-kX-kX = k(Y-2X). So I decided to subtract of 2b times of a from \(a^2+b^2\) to get \(a^2-2ba+b^2\) above, this is all I've done in that step.

\[\gcd(a^2-2ab+b^2,a) = \gcd((a+b)(a-b),a)\]

Next step I took was to factor it (that was my motivation in case you were wondering.)

\[\gcd((a+b)(a-b),a) \le \gcd(a+b,a)*\gcd(a-b,a)\]

Now let's check this out, probably best seen with an example, \(\gcd(8,2)\le \gcd(2,2)*\gcd(4,2)\) which is the same as saying \(2 \le 4\). Basically by separating it apart we get this sort of inequality. This seems spooky, and this is definitely a brave move since inequalities might not help.

\[\gcd(a+b,a)=1\]\[\gcd(a-b,a)=1\]
We know these are true from the reasoning with kY-kX=k(Y-X) from earlier. So hey, if you string it altogether we get:

\[\gcd(a^2+b^2) \le 1\]

Which, since the gcd function can't take any values less than 1, it ends up being equal to 1! I think we can repeat a similar process for b, although maybe not, since I think perhaps the a-b vs b-a term ends up somehow not working out exactly the same. This is just what I did, and I hope it helps but it probably isn't the only way.

Answer 13

I think it works nicely

I notice a small error
a^2 - 2ab + b^2 is not (a +b)(a-b)
but that doest make the proof wrong, the overall structure should work I guess

Answer 14

@Kainui why did you subtract 2ab from left number, but not from right? I kind of understand why you would subtract a, but where does 2b come from?

Answer 15

Or, I get where from is 2a, but I don't get where is b from.

Answer 16

Haha wow yeah, I like don't even know how to multiply I guess anymore. \(a^2-2ab+b^2 = (a-b)^2\).

b is just some number, and it comes from the problem itself.

Answer 17

Oh, so we can subtract anything we want, not only one number from another?

Answer 18

b is a number

Answer 19

Yes.
But why can we subtract it from a^2 + b^2? Is it because GCD(a, b)= 1, so a and b won't have common divisors and that leads to it?

Answer 20

I know it's kinda weird so here, I'll sorta write it in steps of taking away \(a\),

\[\gcd(a^2+b^2,a)\]\[ =\gcd(a^2+b^2-a,a) \]\[=\gcd(a^2+b^2-2*a,a) \]\[=\gcd(a^2+b^2-3*a,a) \]\[=\cdots \]\[=\gcd(a^2+b^2-(2b-1)*a,a)\]\[=\gcd(a^2+b^2-2b*a,a)\]

Answer 21

we could take \(a\) away 3 times, 17 times, whatever. Now let's replace and let's say \(x=3\) and \(y=17\). We can take away \(a\) for \(x\) times too.

The main thing is, we know we aren't taking away more \(a\)s than we have left of \(a^2+b^2\).

Fortunately we know that \(a^2-2ab+b^2 = (a-b)^2 \ge 0\) so we're allowed cause anything squared is greater than or equal to zero.

Answer 22

Okay, I think that I understood it now. :)
Another question: why did you say that GCD(a - b, a) = 1? Is it from the same thing like you wrote there? But GCD(a, a)= a, so how would you subtract b from it, if it's not really possible?

Answer 23

Also, try plugging in some values of \(a\) and \(b\) if you get confused, just make sure whatever you plug in obeys \(\gcd(a,b)=1\). Making up your own concrete examples is always good.

Answer 24

Remember that logs example ?
How gcd can be obtained by taking the difference of the logs...

Answer 25

Yeah so this last bit I was trying to be tricky, and it may or may not work. Luckily we don't have to, since @ganeshie8 pointed out my mistake we actually don't have to worry about this at all. But suppose you still want to worry about it anyways, just for fun. Then think about it :P

Answer 26

I say it won't work because I am specifically forced to assume a > b due to my faulty reasoning in factoring earlier btw

Answer 27

@geneshie8 , yes :) But is it valid to take away a log with length of b from already cut logs into a length pieces? Looking at GCD(a - b, a) ;)
I guess that it would be possible to GCD(b, a) *(-1) = GCD(-b, -a) but then it makes even less sense :/

Oh, that clears up everything, kanui ;)

Answer 28

Try this later maybe

Suppose the logs are of lengths 35 and 14
How are you gona cut them into equal pieces such that the length of the piece is maximum ?

Answer 29

@ganeshie8 yes, gcd would be 7. 35 - 14 = 21 -14 = 7; 14 - 7 = 7; 1st and 2nd numbers of gcd are equal, gcd is equal to 7.

Answer 30

Thank you for your help, everyone! :)

Answer 31

gcd(35, 14) = gcd(35-2*14, 14)

Answer 32

You can subtract any multiple of the other integer. In general
\[\gcd(a,b)= \gcd(a-nb, b)\]

Answer 33

Yes, I didn't notice that b is a multiple of a this time. :)

Answer 34

I challenge you to prove above fact.
You have all the tools necessary to prove by now

Answer 35

Try those proofs when free
I'm sure you will find them fun after doing a few

Answer 36

I accept the challenge! :)
if a > b
gcd(a, b) = gcd(a - nb, b)


gcd(a, b) = p
a = pa`
b = pb`
a - b = pa` - pb` = p(a` - b`) = c

if c > b
gcd(c, b) = gcd(c - b, b)
c - b = p(a` - b`) - pb` = p(a` - 2b`) = d

And if d > b it can be repeated. So, for a = nb (or a` = nb`)
it works to subtract b n times from a.

Is it a good proof?

Answer 37

Brilliant!
But why are you restricting the difference to be positive ? Are you scared of negative numbers ?

Answer 38

Shouldn't gcd function work with only positive values? ;)

Answer 39

gcd(a, b) = gcd(a-nb)

This is true for all integers n, including negatives

Answer 40

Oh, okay. That is addition, in other words. Thanks for pointing it out! :)

Answer 41

In our earlier example

gcd(35, 14) = gcd(35-100*14, 14)

Answer 42

I'd like you to verify above

Answer 43

Well, it works, since gcd(a, b)=gcd(a - nb, b)
And to check if it really works, we can look if gcd(35, 14) = gcd(-1365, 14)
sine gcd(35, 14) = 7, we try to divide -1365 by 7 and we get -195, so it is right! (we know that it is the biggest common divisor and there can't be bigger ones because 14 wouldn't divide from 7 < numbers)

Answer 44

Ofcourse you can't have negative length logs.

gcd can never be negative because any negative integer is always less than 1. And what's special about 1 ?

Answer 45

Looks good, so gcd can be defined for negative integers too even though gcd is never negative

Answer 46

Oh, it was still about logs :D
1 is the least natural divisor. That is why it is special.
gcd(a,b) = 1 would mean that a and b are coprime.

Answer 47

Yes. More importantly 1 is a divisor of every integer.

Answer 48

So there is a natural lower limit for the set of gcds.

Answer 49

I think that slowly I am getting to the point where I start to understand gcd and coprimes a lot better, thanks to you ;)

Answer 50

Np. You're doing great. Keep up the good work :)

Answer 51

Hey did you finish the contradiction proof that I've started earlier ?

Answer 52

I cannot type long replies as I'm on mobile with a cheap touch kb

Answer 53

Nope. I can't see where to go from the step you wrote :/ Should I try a^2 + b^2 - a some times to get p?

Answer 54

No
You see two equations in my reply there

Simply substitute first equation into second

Answer 55

Then stare at the resulting equation
You will see what to do next hopefully

Answer 56

a = pa'
a^2 + b^2 = pc'

Replacing a by pa' gives
(pa')^2 + b^2 = pc'

rearranging gives
b^2 = p(some integer)

That means p divides b.
Contradiction.

Answer 57

Tried to do something similar, but didn't notice that it's contradiction.
But since a and b are coprime wouldnt b = pb` as well? So where does the contradiction come from? @ganeshie8

Answer 58

Oh, from where a and b are coprime and the p would be 1?

Answer 59

We have started with a = pa'


Tell me how can p divide b too ?

Answer 60

We have assumed p is prime. p is not 1.

Answer 61

That is where the contradiction cones from

Answer 62

But well, a and b are coprime... Ohh! Yes, we assumed that a isn't coprime with a^2 + b^2! That's amazing! Your way is quite simple, actually :O Just needed to notice contradiction... thank you very much!

Answer 63

Haha yeah contradiction proofs are always elegant. You may lookup Euclid's proof of infinitude of primes for more motivation :)

Answer 64

Mm, that sounds interesting :) Going to check it out this evening (I noticed that Euclid comes up a lot when talking about primes).

Answer 65

Have fun !