Solution to Frobenius Problem for N=2: Proof?

  • Thread starter adamg
  • Start date
  • Tags
    Frobenius
In summary, the conversation discusses the proof for the Frobenius problem for n=2, where the smallest number that cannot be expressed as a linear combination of two given numbers a and b is (a-1)(b-1). The conversation also discusses a related theorem from Euclid which states that the smallest positive integer expressible as a linear combination of a and b is their greatest common divisor. The conversation also points to a resource for further reading.
  • #1
adamg
48
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
  • #2
Are you sure about that (slightly ungrammatical) statement? 1 is not expressible as a linear combination of 2 and 4?
 
  • #3
This might be what you're looking for: http://www.math.swt.edu/~haz/prob_sets/notes/node11.html [Broken] (Theorem 1.15)
 
Last edited by a moderator:
  • #4
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:

1. What is the Frobenius Problem for N=2?

The Frobenius Problem, also known as the coin problem or the postage stamp problem, asks for the largest integer that cannot be expressed as a linear combination of a given set of positive integer coefficients. For N=2, this means finding the largest integer that cannot be written as the sum of two non-negative multiples of two given integers.

2. What is the significance of finding a solution to the Frobenius Problem for N=2?

Finding a solution to the Frobenius Problem for N=2 has applications in various fields, including number theory, combinatorics, and computer science. It can also be used to solve practical problems, such as determining the minimum number of coins needed to make change for a given amount.

3. How is the solution to the Frobenius Problem for N=2 derived?

The solution to the Frobenius Problem for N=2 can be derived using various methods, including the linear Diophantine equation method, the geometric method, and the greedy algorithm. Each method involves a systematic approach to finding the solution by considering all possible cases and using mathematical principles.

4. What is the proof for the solution to the Frobenius Problem for N=2?

The proof for the solution to the Frobenius Problem for N=2 relies on the concept of the greatest common divisor (GCD). By finding the GCD of the two given integers, the solution can be expressed as a linear combination of the two integers. This proof can be extended to the Frobenius Problem for larger values of N.

5. Are there any limitations or conditions for the solution to the Frobenius Problem for N=2?

Yes, the solution to the Frobenius Problem for N=2 is limited by the values of the given integers. If the GCD of the two integers is 1, then there is no limit to the largest integer that cannot be expressed as a linear combination. However, if the GCD is greater than 1, then there may be certain limitations on the solution.

Similar threads

  • Linear and Abstract Algebra
Replies
3
Views
1K
  • General Math
Replies
7
Views
798
  • General Math
Replies
11
Views
1K
  • General Math
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
83
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
Replies
6
Views
945
  • General Math
Replies
2
Views
1K
  • General Math
Replies
7
Views
392
Back
Top