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
    $\begingroup$ If $28! \equiv -1 \pmod{29}$, what is $27!$ congruent to. And what $26!$? $\endgroup$ – Daniel Fischer 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$ – Bill Dubuque 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}$

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Bill Dubuque 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$ – Bill Dubuque 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.

| cite | improve this answer | |
$\endgroup$
  • $\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.