Is There a Contradiction in the Brain Teaser with Positive Integers x and y?

  • Context: High School 
  • Thread starter Thread starter 1+1=1
  • Start date Start date
  • Tags Tags
    Brain Exercises Love
Click For Summary
SUMMARY

The discussion centers on the mathematical proof that for any positive integers x and y, there exists a positive integer r such that rx is greater than or equal to y. The proof utilizes the concept of a set S defined as {y - rx | r in Z+}, demonstrating that if y is less than rx for all r, then S must contain a least element, leading to a contradiction. This contradiction confirms that the original assumption is false, thereby establishing the validity of the statement.

PREREQUISITES
  • Understanding of positive integers and basic number theory
  • Familiarity with mathematical proofs and contradiction techniques
  • Knowledge of set theory and least element properties
  • Basic algebraic manipulation skills
NEXT STEPS
  • Study the concept of mathematical induction and its applications
  • Learn about the properties of integers and their implications in proofs
  • Explore advanced topics in number theory, such as Diophantine equations
  • Investigate the role of contradiction in mathematical logic
USEFUL FOR

Mathematicians, students studying number theory, educators teaching proof techniques, and anyone interested in logical reasoning and mathematical problem-solving.

1+1=1
Messages
93
Reaction score
0
if x and y are pos. int. then rx >=y. x is an int. help!
 
Physics news on Phys.org
What is the question ?

If x, y are positive integers, there can always be found an r such that rx >= y. (Why repeat "x is an integer" ?) Do you want a proof of the above statement ?
 
Assume that y > rx , for all r

Then the set S = {y-rx| r in Z+} consists only of positive numbers. So, S must possesses a least element, say y-mx.

But y-(m+1)x also belongs in S, since m+1 is in Z+ if m is.

y-(m+1)x = y-mx - x < y - mx, since x>0, contrary to our choice of the minimal element - a contradiction !

Hence, the assumption was false.
 

Similar threads

High School Solving a Linear Programming Problem which Requires Integer Solutions
  • · Replies 17 ·
Replies
17
Views
4K
High School Solving for the Nth divergence in any coordinate system
  • · Replies 41 ·
2
Replies
41
Views
5K
High School Find All Positive Integer Pairs for (x, y) in sqrt[3]{7x^2-13xy+7y^2}=|x-y|+1
  • · Replies 1 ·
Replies
1
Views
2K
MHB Positive Integer Solutions of $(x^2+y^2)^n=(xy)^{2014}$
  • · Replies 2 ·
Replies
2
Views
3K
High School Very simple exercises in General Relativity
  • · Replies 57 ·
2
Replies
57
Views
5K
High School Can x(x+y) Be Proved to Be ≤ 2 for Positive Real Numbers?
  • · Replies 11 ·
Replies
11
Views
3K
High School How Many Integer Solutions Exist for the Equation |x|+|y|+|z|=2010?
  • · Replies 2 ·
Replies
2
Views
3K
Graduate Finding Positive Integers for Irrational Number Interval
  • · Replies 1 ·
Replies
1
Views
3K
High School Is the Quotient Topology of Real Numbers Homeomorphic to Real Numbers?
  • · Replies 6 ·
Replies
6
Views
3K
High School How Can You Minimize This Complex Square Root Expression for Positive x and y?
  • · Replies 6 ·
Replies
6
Views
2K