Solution to Frobenius Problem for N=2: Proof?

  • Thread starter Thread starter adamg
  • Start date Start date
  • Tags Tags
    Frobenius
Click For Summary
SUMMARY

The Frobenius Problem for N=2 states that the smallest integer that cannot be expressed as a linear combination of two coprime integers \(a\) and \(b\) is given by the formula \((a-1)(b-1)\). This conclusion is supported by Theorem 1.15 from the referenced source, which clarifies that the smallest positive integer expressible as a linear combination of \(a\) and \(b\) is their greatest common divisor (gcd). The discussion emphasizes the importance of distinguishing between positive and non-positive linear combinations.

PREREQUISITES
  • Understanding of linear combinations in number theory
  • Familiarity with the concept of coprime integers
  • Knowledge of the greatest common divisor (gcd)
  • Basic comprehension of mathematical proofs and theorems
NEXT STEPS
  • Study the proof of the Frobenius Coin Problem for two variables
  • Explore the implications of Theorem 1.15 in number theory
  • Learn about the properties of coprime integers and their applications
  • Investigate Euclid's algorithm for finding the gcd of two integers
USEFUL FOR

Mathematicians, students studying number theory, and anyone interested in combinatorial optimization and integer programming.

adamg
Messages
48
Reaction score
0
does anyone know a proof for the solution to the frobenius problem for n=2? that is, that the smallest not possible number expressable as a linear combination of a and b is (a-1)(b-1)??
 
Mathematics news on Phys.org
Are you sure about that (slightly ungrammatical) statement? 1 is not expressible as a linear combination of 2 and 4?
 
This might be what you're looking for: http://www.math.swt.edu/~haz/prob_sets/notes/node11.html (Theorem 1.15)
 
Last edited by a moderator:
the smallest positive integer expressible as a linear combination of a and b is their gcd. this is in euclid. oh you had the essential word backwards. and also you seem to have meant positive inear combination.
 
Last edited:

Similar threads

Undergrad Final part of proof of timelike Killing w/ Frobenius --> static
  • · Replies 1 ·
Replies
1
Views
972
Variations of the Frobenius coin problem
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad Problem with notation of matrix elements
  • · Replies 3 ·
Replies
3
Views
2K
High School Difference between like powers proof
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad About the maximal extension of local charts on a manifold
  • · Replies 8 ·
Replies
8
Views
1K
Undergrad Proof of Differences of Odd Powers
  • · Replies 11 ·
Replies
11
Views
2K
Graduate Searching for radial part solution of Klein-Gordon type equation
  • · Replies 1 ·
Replies
1
Views
2K
Question about the Frobenius method and Bessel functions
  • · Replies 4 ·
Replies
4
Views
3K
Insights Fermat's Last Theorem
  • · Replies 105 ·
4
Replies
105
Views
8K
Finding 2 solutions of this Bessel's function using a power series
  • · Replies 8 ·
Replies
8
Views
2K