Elementary Number Theory - GCD problems and proofs

[Amcote]

Problem 1
Suppose ab=cd, where a, b, c d $\in$ N. Prove that a$^{2}$+b$^{2}$+c$^{2}$+d$^{2}$ is composite.

Attempt
ab=cd suggests that a=xy, b=zt, c=xz. d=yt. xyzt=xzyt.

So (xy)$^{2}$+(zt)$^{2}$+(xz)$^{2}$+(yt)$^{2}$=x$^{2}$(y$^{2}$+z$^{2}$)+t$^{2}$(z$^{2}$+y$^{2}$)=(x$^{2}$+t$^{2}$)(z$^{2}$+y$^{2}$) Therefore this is composite.


Problem 2

Prove that

GCD(a,b)=1 $\Rightarrow$ GCD(a+b,a-b,ab)=1.

Attempt

My first attempt at this I started with (a+b,a-b,ab)=1 and wrote this as a linear combination (a+b)x+(a-b)y+(ab)z=1 which can be re written as a(x+y+bz)+b(x-y)=1 and I thought I had proved it but realized the arrow suggests a one way proof so now I am stuck at how to start with (a,b)=1... Perhaps if I take ax+by=1 and square both sides but after that I still don't know what to do. Any hints would be appreciated.

Problem 3

Prove that if a,m $\in$ N and a>1, then

GCD($\frac{a^{m}-1}{a-1}$,a-1)=GCD(a-1,m).

Attempt
I'm having a really bad day with these sorts of questions and any attempt just turns into a mess so any little suggestion or hint would be appreciated for this one as well.

Thank you

 

[SammyS]

Problem 1
Suppose ab=cd, where a, b, c d $\in$ N. Prove that a$^{2}$+b$^{2}$+c$^{2}$+d$^{2}$ is composite.

Attempt
ab=cd suggests that a=xy, b=zt, c=xz. d=yt. xyzt=xzyt.

So (xy)$^{2}$+(zt)$^{2}$+(xz)$^{2}$+(yt)$^{2}$=x$^{2}$(y$^{2}$+z$^{2}$)+t$^{2}$(z$^{2}$+y$^{2}$)=(x$^{2}$+t$^{2}$)(z$^{2}$+y$^{2}$) Therefore this is composite.

...

Thank you

It's not clear to me how you justify the following:

" ab=cd suggests that a=xy, b=zt, c=xz. d=yt. "​

Can you explain this?

 

[Amcote]

Basically because for whatever you choose x,y,z and t to be, ab=cd will always be true.

 

[SammyS]

Basically because for whatever you choose x,y,z and t to be, ab=cd will always be true.

That's correct, but for a proof, it's often required to justify such a statement.

 

[Joffan]

I am probably missing some simple equivalences, but I can solve #2 by first considering k=GCD(a+b,a-b) in two cases and then showing that GCD(k, ab) must be 1 for both cases.

edit to add: For #3, consider a^k mod (a-1)

 

[Amcote]

Further attempt for number 2:

suppose d=gcd(a+b,a-b,ab),
therefore d|a+b, d|a-b, d|ab
and also d|(a+b+a-b)=2a and d|(a+b-[a-b])=2b
So d|gcd(2a,2b)
but since gcd(a,b)=1 --> 2*gcd(a,b)=2 --> gcd(2a,2b)=2
so from this d|2 and so d=1 or d=2
from here it is the "ab" that is bugging me and will probably show me that d must be 1. But I don't know how to finish this.

 

[Joffan]

Edit to insert: You might as well define d=gcd(a+b,a-b) Nothing you have derived about it relies on the ab coefficient. Then the value you are finally looking for is gcd(d,ab). To continue, consider two cases:

if a+b is odd...
if a+b is even...