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...
@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 :
$\displaystyle 1476=1474+2=11 \times 134+2$
$\displaystyle \implies 2=1476+(-134) \times 11$
$\displaystyle 11=2 \times 5+\boxed{1}$
$\displaystyle \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 !
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 : (
Hmmm
The problem is that $\displaystyle 1557=3^2 \cdot 173$
So $\displaystyle \phi(1557)=\phi(3^2) \cdot \phi(173)$
If p is prime, $\displaystyle \phi(p^a)=p^{a-1}(p-1)$
--> $\displaystyle \phi(3^2)=6$
-------> $\displaystyle \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 $\displaystyle (\mathbb{Z}/1557\mathbb{Z},\cdot)$, that is to say the least integer m such that $\displaystyle a^m \equiv 1 \mod 1557$, divides 1032.
How long is your list ?