• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter Ceci020
  • Start date
  • #1
11
0
** Homework Statement
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.
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
618


If you have the Euclidean algorithm, then use it! Pick n=q1. n*a<b right? Why is (n+1)*a>b?
 

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

Replies
6
Views
3K
Replies
13
Views
2K
Replies
3
Views
1K
Replies
4
Views
731
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
7
Views
2K
Top