# Elementary Number Theory - GCD problems and proofs

1. Jun 7, 2014

### 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

2. Jun 8, 2014

### SammyS

Staff Emeritus
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?

3. Jun 8, 2014

### Amcote

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

4. Jun 8, 2014

### SammyS

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

5. Jun 9, 2014

### 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 ak mod (a-1)

Last edited: Jun 9, 2014
6. Jun 10, 2014

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

7. Jun 10, 2014

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

Last edited: Jun 10, 2014