# [SOLVED] Finding the sum of two unknown variables

Printable View

• Jun 30th 2008, 10:26 AM
Chop Suey
[SOLVED] Finding the sum of two unknown variables
Hello everyone,
Quote:

Given that $\displaystyle 43p + 23q = 4323$, find $\displaystyle p + q$?
The question is to find the sum of the unknown variables. Now, the variables have to be integers, and as you can see from the easy example I made, the sum could be $\displaystyle 43(100) + 23(1)=4323$ $\displaystyle \Rightarrow p+q = 101$

Of course, this is not the only solution. Try the following:

$\displaystyle 43(54) + 23(87) = 4323$
$\displaystyle \Longrightarrow p + q = 141$

I suspect that there are even more integer solutions to this equation. My method for finding the values is the old simple bruteforce "technique", where I divide 4323 by highest coefficient and that's where I get a headstart. You can of course find out the pattern, but these "cooked" equations are no good for learning.

My question is: is there a logical process of solving for $\displaystyle p + q$? Other than bruteforce, of course. I asked my teacher today, and he just said "that's number theory." I looked up number theory, but I was kind of lost.

These type of questions are pretty common on the SAT I tests, and I love them. My brother and I used to exchange multivariable equations like that and try to find the sum all the time.
• Jun 30th 2008, 10:56 AM
Moo
Hello,

What comes in my mind is that we have to solve for p and q before finding p+q... maybe there is another method...
This comes with the Euclidian algorithm, which will yield to Bézout's theorem (google for them).

43 & 23 are coprime, that is to say they have no common divider.
The theorem states that if 43 and 23 are coprime, then we can write it :
$\displaystyle 43u+23v=1$, where u & v are integers (positive or negative).

-------------------------
Now, the thing is that you have to find a particular solution to the equation $\displaystyle 43u+23v=1$, thanks to the Euclidian algorithm.

$\displaystyle 43=23*1+20 \implies 20=43-23$

$\displaystyle 23=20*1+3 \implies 3=23-20=23-(43-23)=-43+2*23$

$\displaystyle 20=3*6+2 \implies 2=20-3*6=(43-23)-6*(-43+2*23)=7*43-13*23$

$\displaystyle 3=2+1 \implies 1=3-2=(-43+2*23)-(7*43-13*23)=-8*43+15*23$

Thus $\displaystyle \boxed{u=-8 \text{ and } v=15}$

--------------------------
What's good with it is that we can multiply the equation $\displaystyle 43u+23v=1$ by 4323 in order to get a particular solution for p and q in $\displaystyle 43p+23q=4323$

--> $\displaystyle \boxed{p_1=-8*4323=-34584 \text{ and } q_1=15*4323=64845}$

---------------------------
MOO

So we have :

\displaystyle \begin{aligned} 4323&={\color{red}43}*p_1+{\color{red}23}*q_1 \\ &={\color{red}43}*p+{\color{red}23}*q \end{aligned}

$\displaystyle 43p_1+23q_1=43p+23q$

$\displaystyle 43(p-p_1)=23(q_1-q)$

Because 43 and 23 are coprime, we know by the Gauss theorem, that $\displaystyle q_1-q=43k$ and $\displaystyle p-p_1=23k$, $\displaystyle \forall \text{ integer (positive or negative) } k.$

Therefore the general solution is :

$\displaystyle p=p_1+23k$
$\displaystyle q=q_1-43k$

$\displaystyle \boxed{p+q=p_1+q_1-20k}$

Remember, $\displaystyle p_1=-34584$ and $\displaystyle q_1=64845$

------------------------------

$\displaystyle p_1$ and $\displaystyle q_1$ are ugly because 4323 is a large number, and I showed a general method.

If you have got a particular solution (100 and 1), set up $\displaystyle p_1=100$ and $\displaystyle q_1=1$ and take it from the red MOO. (Rofl)

I hope this is clear enough... If you have any question...
• Jun 30th 2008, 11:00 AM
Soroban
Hello, Chop Suey!

Here's a rather primitive solution . . .

Quote:

Given that: .$\displaystyle 43p + 23q =\: \:4323$, find $\displaystyle p + q.$

We have: .$\displaystyle 43p + 23q \:=\:43(100) + 23 \quad\Rightarrow\quad 23q - 23 \:=\:43(100) - 43p$

Factor: .$\displaystyle 23(q-1) \:=\:43(100-p) \quad\Rightarrow\quad q \;=\;\frac{43(100-p)}{23} + 1$

Since $\displaystyle q$ is an integer, $\displaystyle (100-p)$ must be divisible by 23.

This happens for: .$\displaystyle p \;=\;100,\:77,\:54,\:31\:\hdots \:100-23t$
. . .and we have: .$\displaystyle q \;=\;1,\:44,\:87,\:130,\:\hdots\:1 + 43t$

Therefore: .$\displaystyle p+q \;=\;(100-23t) + (1 + 43t) \;=\;101 + 20t\:\text{ for any integer }t$

• Jun 30th 2008, 11:08 AM
Chop Suey
I want to thank both of you, Moo and Soroban, for the astoundingly fast reply.

Moo: I'm going to look up those theorems you mentioned and discuss this further should I have any questions.

Soroban: It may be primitive, but you made me wish if I only approached this method before.

Thanks again :D
• Jun 30th 2008, 11:14 AM
Moo
Here are the wikipedia links (so that you won't be mistaken :)) :

Bézout's identity/lemma (not really theorem actually) : Bézout's identity - Wikipedia, the free encyclopedia

The way I used the Euclidian algorithm : Extended Euclidean algorithm - Wikipedia, the free encyclopedia

Ok...Gauss theorem = Euclid's lemma (Tongueout) (they're the same, but I don't know the circumstances that made 2 different names lol)

Quote:

If a positive integer divides the product of two other positive integers, and the first and second integers are coprime, then the first integer divides the third integer.
This can be written in notation:
If n|ab and gcd(n,a) = 1 then n|b.
Euclid's lemma - Wikipedia, the free encyclopedia