# Thread: linear combination equation help

1. ## linear combination equation help

11u - 1476v =1

I have done everyhing to get a value that works this out, I can't seem to get my self with it here...

2. Originally Posted by duggaboy
11u - 1476v =1

I have done everyhing to get a value that works this out, I can't seem to get my self with it here...
not enough information. what exactly do you want to find? what do u and v represent?

3. I need u in order to solve another equation.....its of the form ax - by =1
11 is my k, and 1476 is my phi of m my m is 1577 which is my modulo

4. Originally Posted by duggaboy
I need u in order to solve another equation.....its of the form ax - by =1
11 is my k, and 1476 is my phi of m my m is 1577 which is my modulo
ok, you confused me even more. please state the original problem in it's entirety. you have one equation with two unknowns. we can come up with infinite solutions. we need something to narrow down our options, since it seems you want a particular u

5. @Jhevon : this is number theory

We're working on integers

Since 11 and 1476 are coprime, there exists u and v that verify this equality (Bézout's identity)

Now use the Euclidian algorithm, which lets us say that at a moment, there will be 1 as the reminder :

$1476=1474+2=11 \times 134+2$

$\implies 2=1476+(-134) \times 11$

$11=2 \times 5+\boxed{1}$

\begin{aligned} \implies 1 &=11+2 \times (-5) \\
&=11+(-5) \times (1476+(-134) \times 11) \\
&=11+(-5) \times 1476+670 \times 11 \\
1&= \boxed{\textbf{671} \times 11-\textbf{5} \times 1476} \end{aligned}

And this last expression gives you u and v
If you're looking for the general solution, tell us !

6. Yes that is what I need....THANK YOU SO MUCH....I have to use that to decode an encoded message..

7. Originally Posted by duggaboy
Yes that is what I need....THANK YOU SO MUCH....I have to use that to decode an encoded message..
Wait, I'm lost here
Is what I did what you want or do you want the general solution ?

You ought to memorize this method for finding u and v..

8. I think that is what i need....I needed to solve for u, I still can't do the problem because now the equation looks like this:

a^u = = b (mod m) where a is my list to decode and u=671 m=1557

I'm lost when it comes to raising somthing to the 671 power....and my formula for mods it would take me weeks....So I just can't figure this one out : (

9. Hmmm

The problem is that $1557=3^2 \cdot 173$

So $\phi(1557)=\phi(3^2) \cdot \phi(173)$

If p is prime, $\phi(p^a)=p^{a-1}(p-1)$
--> $\phi(3^2)=6$

-------> $\phi(1557)=6 \cdot 172=1032 \neq 1476$

But I don't think you have to do it this way... You can use the fact that if a is coprime (I don't remember what happens if it is not) with 1557, the order of a in $(\mathbb{Z}/1557\mathbb{Z},\cdot)$, that is to say the least integer m such that $a^m \equiv 1 \mod 1557$, divides 1032.

How long is your list ?