# Thread: [SOLVED] Finding the sum of two unknown variables

1. ## [SOLVED] Finding the sum of two unknown variables

Hello everyone,
Given that $43p + 23q = 4323$, find $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 $43(100) + 23(1)=4323$ $\Rightarrow p+q = 101$

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

$43(54) + 23(87) = 4323$
$\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 $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.

2. 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 :
$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 $43u+23v=1$, thanks to the Euclidian algorithm.

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

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

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

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

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

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

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

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

So we have :

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

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

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

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

Therefore the general solution is :

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

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

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

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

$p_1$ and $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 $p_1=100$ and $q_1=1$ and take it from the red MOO.

I hope this is clear enough... If you have any question...

3. Hello, Chop Suey!

Here's a rather primitive solution . . .

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

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

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

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

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

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

4. 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

5. 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 (they're the same, but I don't know the circumstances that made 2 different names lol)

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