2
$\begingroup$

Find the remainder when $2(26!)$ is divided by $29$.

So I know I'm going to use Wilson's theorem and then I would have $28!=-1(\mod29\:)$ but what is the next step? Step by Step explanation please!

$\endgroup$
4
  • 4
    $\begingroup$ If $28! \equiv -1 \pmod{29}$, what is $27!$ congruent to. And what $26!$? $\endgroup$ May 12 '14 at 22:20
  • $\begingroup$ 27!≡-1 (mod 28), 26!≡-1(mod27) correct? $\endgroup$
    – Lil
    May 12 '14 at 22:23
  • $\begingroup$ See also math.stackexchange.com/questions/99876/…. $\endgroup$
    – lhf
    May 12 '14 at 22:26
  • 1
    $\begingroup$ @lhf See also this answer. $\endgroup$ May 12 '14 at 22:36
4
$\begingroup$

$\begin{eqnarray} {\bf Hint}\ \ \ {\rm mod}\ 29\!:\,\ {-}1\! \overset{\rm Wilson}\equiv 28!\, \equiv &&\ (\color{#c00}{28})\ (\color{#0a0}{27})26!\\ \equiv&& (\color{#c00}{-1})(\color{#0a0}{-2}) 26!\\ \equiv &&\qquad\ \ \,2\cdot 26!\end{eqnarray}$

$\endgroup$
4
  • $\begingroup$ where did the -1 and -2 come from? is it 28-29 and 27-29? $\endgroup$
    – Lil
    May 12 '14 at 22:26
  • $\begingroup$ @Lil mod $\,29\!:\ 28\equiv -1\,$ by $\,20\mid 28-(-1)\ $ and $\ 27\equiv -2\,$ by $\,29\mid 27-(-2)\ \ $ $\endgroup$ May 12 '14 at 22:27
  • $\begingroup$ ok after that would I multiply (-1)(-2) and get 2(26!)≡−1mod29 $\endgroup$
    – Lil
    May 12 '14 at 22:29
  • $\begingroup$ @Lil Exactly, just as I wrote above. $\endgroup$ May 12 '14 at 22:30
1
$\begingroup$

$$28!\equiv -1\bmod 29$$ or $$28\cdot27 \cdot 26!\equiv -1\bmod 29$$ which is $$2\cdot 14\cdot27 \cdot 26!\equiv -1\bmod 29$$ Now let $a$ and $b$ be modular inverses of $14,27$ respectively.(such $a,b$ exist because $gcd(14,29)=1$ and $gcd(27,29)=1$).

Multiply both sides by $a\cdot b$. The result is what you want.

$\endgroup$
2
  • $\begingroup$ how did you change 28 to 2, 27 to 14? $\endgroup$
    – Lil
    May 12 '14 at 22:24
  • $\begingroup$ $28=2\cdot 14$. $\endgroup$
    – Fermat
    May 12 '14 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.