1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Elementary Number Theory - GCD problems and proofs

  1. Jun 7, 2014 #1
    Problem 1
    Suppose ab=cd, where a, b, c d [itex]\in[/itex] N. Prove that a[itex]^{2}[/itex]+b[itex]^{2}[/itex]+c[itex]^{2}[/itex]+d[itex]^{2}[/itex] is composite.

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

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


    Problem 2

    Prove that

    GCD(a,b)=1 [itex]\Rightarrow[/itex] 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 [itex]\in[/itex] N and a>1, then

    GCD([itex]\frac{a^{m}-1}{a-1}[/itex],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. jcsd
  3. Jun 8, 2014 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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?
     
  4. Jun 8, 2014 #3
    Basically because for whatever you choose x,y,z and t to be, ab=cd will always be true.
     
  5. Jun 8, 2014 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    That's correct, but for a proof, it's often required to justify such a statement.
     
  6. Jun 9, 2014 #5
    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
  7. Jun 10, 2014 #6
    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.
     
  8. Jun 10, 2014 #7
    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Elementary Number Theory - GCD problems and proofs
Loading...