How much is modulus( 3214020402^43424492897 , 308 )?

Question

Let $$B=3214020402$$ $$E=43424492897$$ $$A=B^E$$

How much is modulus( A , 308 ) ?

My try: $$[A]_{308} \to ([B]_4^E,[B]_7^E,[B]_{11}^E) = ([2]_4^E,[5]_7^E,[10]_{11}^E)$$

Applying Eulero-Fermat Rule to each member led me to solve this Chinese System:

$$ \left\{ \begin{array} xx=0 \mod 4\\ x=10 \mod 11\\ x=1 \mod 7 \end{array} \right. $$

Whose solution is 408 and $$[408]_{308} = 120$$ (which should be the answer). Is it correct?

http://www.wolframalpha.com/input/?i=3214020402^43424492897+mod+308 See for your self. I'm not entirely sure if my input is correct, but wolframalpha will surely be able to handle it. — Mixxiphoid, Jan 22 '14 at 12:08
Should be $x = 3 \pmod 7 \implies x = 164 \pmod{308}$ instead. — achille hui, Jan 22 '14 at 12:18
But because of Eulero-Fermat $$5^6 = 1 (mod 7)$$ and $$E = 0 (mod 6)$$. What am I missing? — Angelo Tricarico, Jan 22 '14 at 12:32
You are right, my calculator can handle only 10 length numbers, so the last 7 was a 0 for the calculator. Thanks. — Angelo Tricarico, Jan 22 '14 at 13:44

score 1 · Answer 1 · answered Jan 22 '14 at 15:49

There is an error. Modulo $\,7\,$ we have $\,B^E \equiv \color{#c00}3\,$ (not $1),\,$ see below.

${\rm mod}\ 4\!:\ \ 2^2\equiv\ 0\ \, \Rightarrow\, \ B^E\ \equiv\ 2^2\equiv 0\iff B^E = 4k$

${\rm mod}\ 7\!:\ \ 2^3\equiv\ 1\ \, \Rightarrow\,\ B^E \equiv (-2)^2 \equiv\, \color{#c00}3 $

${\rm mod}\ 11\!: 2^5\equiv -1\,\Rightarrow\, B^E \equiv (-1)^{\rm odd}\equiv \color{#0a0}{-1}.\ $ Let's solve these three prior congruences:

${\rm mod}\ 11\!:\ B^E = 4k\equiv \color{#0a0}{-1}\equiv -12\!\iff\! k\equiv -3\!\iff\! k = -3\!+\!11j\!\iff\! B^E=4k=\color{blue}{-12\!+\!44j}$

${\rm mod}\ 7\!:\,\ \color{#c00}3\equiv B^E = \color{blue}{-12\!+\!44j} \equiv 2+2j\!\iff\! 2j\equiv 1\equiv 8\!\iff\! j\equiv 4\!\iff\! j = \color{purple}{4+7n}$

Therefore $\quad\ B^E = -12\!+\!44j = -12+44(\color{purple}{4+7n})\, =\, 164\ +\ 4\cdot 7\cdot 11\, n$

Yep, we did find the issue in the comments, anyway could you explain by words what happened from "see below." to "Let's solve"? — Angelo Tricarico, Jan 22 '14 at 16:48
@Deleted All three use $\ B\equiv b,,\ b^n\equiv 1\ \Rightarrow\ B^E\equiv b^E\equiv b^{\large E\ {\rm mod}\ n}.\ \ $ If you'd like more detail then let me know. — Bill Dubuque, Jan 22 '14 at 16:58

How much is modulus( 3214020402^43424492897 , 308 )?

1 Answers1