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!

Prove: there exists n in N such that na < b and (n+1)a > b, known a does not divide b

  1. Nov 20, 2011 #1
    ** The problem statement, all variables and given/known data
    Question is to prove:
    If 1 < a < b and if a does not divide b
    then there exists n in N such that na < b and (n+1)a > b

    ** My thoughts:
    Since a does not divide b for 1 < a < b, I want to refer to the Euclidean algorithm, so:
    b = q1 * a + r1 for r1 is the first remainder, and r1 < a

    But then I get lost on where to go from here. Actually I thought of using induction for my proof, where I define a set S = {n in N such that na < b and (n+1)a > b}. But when I do the 2nd claim: if n in S, then n+1 in S, I think I find a contradiction because when replace n+1 to n for the first part of the def. of S, (n+1)a < b is false.

    So could someone please give me some hints on how should I proceed?
    Thank you very much for your help.
     
  2. jcsd
  3. Nov 20, 2011 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Prove: there exists n in N such that na < b and (n+1)a > b, known a does not divi

    If you have the Euclidean algorithm, then use it! Pick n=q1. n*a<b right? Why is (n+1)*a>b?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove: there exists n in N such that na < b and (n+1)a > b, known a does not divide b
  1. Is (a,b) open in R^n (Replies: 2)

  2. Lim a(n)b(n) = AB (Replies: 2)

Loading...