# A number theory puzzle

• Sep 15th 2010, 07:10 AM
wonderboy1953
A number theory puzzle
I give you 7x - 17y = 1. Now give me back how many solution pairs (in natural numbers) there are for the equation? For example (5,2) and (22,9) are solutions (if you can't figure this one out in a week, I'll drop a hint and if you still can't solve it after another week, then I'll solve it for you).
• Sep 15th 2010, 07:19 AM
undefined
Quote:

Originally Posted by wonderboy1953
I give you 7x - 7y = 1. Now give me back how many solution pairs (in natural numbers) there are for the equation? For example (5,2) and (22,9) are solutions (if you can't figure this one out in a week, I'll drop a hint and if you still can't solve it after another week, then I'll solve it for you).

Typo? 7*5 - 7*2 most definitely does not equal 1. :)

In fact it is easily shown that 7x - 7y = 1 has no integer solutions; the LHS is a multiple of 7 while the RHS is not.
• Sep 15th 2010, 07:26 AM
wonderboy1953
Quote:

Originally Posted by undefined
Typo? 7*5 - 7*2 most definitely does not equal 1. :)

In fact it is easily shown that 7x - 7y = 1 has no integer solutions; the LHS is a multiple of 7 while the RHS is not.

• Sep 15th 2010, 07:37 AM
undefined
Quote:

Originally Posted by wonderboy1953
I give you 7x - 17y = 1. Now give me back how many solution pairs (in natural numbers) there are for the equation? For example (5,2) and (22,9) are solutions (if you can't figure this one out in a week, I'll drop a hint and if you still can't solve it after another week, then I'll solve it for you).

We have Bezout's identity with a sign change. There are infinite solutions, and a solution exists iff x > 4 and $x\equiv 5\pmod{17}$.

For $k \ge 0$ we solve for y

7*(17k + 5) - 17y = 1

7*17k + 35 - 17y = 1

17y = 7*17k + 34

y = 7k + 2

So the solution set is given by (x,y) = (5 + 17k, 2 + 7k) where k ranges over the non-negative integers.
• Sep 15th 2010, 07:56 AM
wonderboy1953
That's the solution using parametric equations.
• Sep 15th 2010, 12:34 PM
Wilmer
Methinks Sir Diophantine just turned over in his grave.
• Sep 15th 2010, 12:38 PM
undefined
Quote:

Originally Posted by Wilmer
Methinks Sir Diophantine just turned over in his grave.

I realize my solving for y could be shortened realizing that

7(x + 17) - 17(y + 7) = 7x - 17y

but what exactly are you referring to?
• Sep 15th 2010, 01:15 PM
wonderboy1953
Quote:

Originally Posted by Wilmer
Methinks Sir Diophantine just turned over in his grave.

Certainly not English.
• Sep 16th 2010, 07:48 AM
Soroban
Hello, wonderboy1953!

I have a very elementary solution . . .

Quote:

$\text{Given: }\;7x - 17y \:=\: 1$

$\text{How many solutions in natural numbers are there for the equation?}$

Answer: there are a brizillian solutions.

Solve for $x\!:\;\;x \:=\:\dfrac{17y+1}{7} \;=\;2y + \dfrac{3y+1}{7}$

Since $\,x$ is a natural number, $(3y+1)$ must be divisible by 7.

We find that: . $y \;=\;2,\,9,\,16,\,\hdots,\,7t-5\;\text{ for }t \in N$

Then: . $x \;=\;2(7t-5) + \dfrac{3(7t-5)+1}{7} \;=\;17t - 12$

Solutions: . $\begin{Bmatrix}x &=& 17t - 12 \\ y &=& 7t-5 \end{Bmatrix}\;\;\text{ for }t \in N$

Of course, this is basicaly undefined's solution.
• Sep 16th 2010, 09:46 AM
Wilmer
Quote:

Originally Posted by undefined
I realize my solving for y could be shortened realizing that
7(x + 17) - 17(y + 7) = 7x - 17y
but what exactly are you referring to?

Nothing in particular UnD; I had just skimmed over:
Diophantine Equations
and saw WB's equation...