We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The important part is that we're only interested in integer ("whole number") solutions. In this case, the Diophantine equation is
n = 5x + 3y
and we only care about cases where x and y are both integers. For example, if n were 11, we don't care about the solution x=1.6, y=1. We're only interested in the solutions like x=1, y=2.
Sherlock and The Beast
You are viewing a single comment's thread. Return to all comments →
It's a great solution. If I understand correctly, you separate N in two numbers: a multiple of 3 and a multiple of 5.
Is there a name to this mathematical procedure ?
It is called a linear combination. In this case, it is a linear combination of 3 and 5.
More specifically it is a Diophantine equation.
DioPhantine is A * * 2 + b * * 2 = c * * 2 but this seems like A * x + B * x = C where x > 0 || y > 0 am i wrong to argue you on this?
A Diophantine equation is simply one in which we are only interested in integer solutions. This is known as a linear Diophantine equation.
so a linear equation is part of the set of Diophatine equations. Thanks! I didn't quite get that at first.
The important part is that we're only interested in integer ("whole number") solutions. In this case, the Diophantine equation is
n = 5x + 3y
and we only care about cases where x and y are both integers. For example, if n were 11, we don't care about the solution x=1.6, y=1. We're only interested in the solutions like x=1, y=2.
There is an alternative solution, but not so efficient (but still O(1) in spite of recursion) and not so elegant as the Diophantine equation. This is linear congruence equation: 5x = n (mod 3). You can solve it by means of the extended Euclidean algorithm. I am aware that this is like 'A sledgehammer to crack a nut', but fyi. Here you can practise with the linear congruence.
Thank you mang, appreciate the reply :)