1
$\begingroup$

given $2^{60}\equiv1\bmod{61}$ and $60! \equiv-1\bmod{61}$ How we can deduce:

$$2^{60}\cdot3\equiv60!\cdot x\bmod61 \Rightarrow3\equiv-x\bmod61$$

This is part of a book but author doesn't explain.

$\endgroup$
2
  • $\begingroup$ This is pretty much immediate with a couple of substitutions. Because $a\equiv b\bmod c\implies ad\equiv bd\bmod c$. $\endgroup$ – Chris Custer Jan 23 at 6:09
  • $\begingroup$ How can we not? $2^{60}\equiv 1$ and $60!\equiv -1$ so $2^{60}\cdot 3\equiv 1\cdot 3$ and $60!\cdot x \equiv -1\cdot x$. $\endgroup$ – fleablood Jan 23 at 6:35
4
$\begingroup$

$$2^{60}\cdot3\equiv60!\cdot x\pmod{61}$$

Just replace $2^{60}\equiv1, 60!\equiv-1$ to find

$$1\cdot3\equiv(-1)\cdot x\pmod{61}$$

$$\iff x\equiv-3\equiv-3+61$$

$\endgroup$
2
$\begingroup$

The author did not explain because this is a simple matter of substituting the residues for $2^{60}$ and $60!$ into the equation $2^{60}\cdot3\equiv60!\cdot x\bmod61$.

$\endgroup$
2
$\begingroup$

The integers modulo any prime, including $61$, are a field, so every nonzero element has an inverse. Just plug in what you are given $$2^{60} \cdot 3 \equiv 60! \cdot x \pmod {61}\\ 1 \cdot 3 \equiv -1 \cdot x \pmod {61}\\ 3 \equiv -x \pmod {61}$$

$\endgroup$
3
  • $\begingroup$ Thanks. If I have problem understanding such an easy material how I'm supposed to know about fields? $\endgroup$ – Xaqron Jan 23 at 6:04
  • $\begingroup$ You gave no indication of what you know and what you don't. As it turns out, that is not important. $\endgroup$ – Ross Millikan Jan 23 at 6:05
  • $\begingroup$ I appreciate your time and patience. $\endgroup$ – Xaqron Jan 23 at 6:06

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