1

Came across an expression given below

$$321^{984} \equiv 6^{984} \equiv(-1)^{984}\equiv 1 \pmod{7}$$

Now $321^{984} \equiv 6^{984} \pmod{n}$ is understood

and $6^{984} \equiv (-1)^{984} \equiv 1^{984} \pmod{n} \equiv 1 \pmod{n}$

but then how is $321^{984} \equiv 1 \pmod{n}$ ?

I know that if

$a\equiv b \pmod{n}$ and $c \equiv d \pmod{n}$ then

$a+c \equiv b+d \pmod{n}$ or

$ac \equiv bd \pmod{n}$

But Equation (I) looks something of the type

$a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$ then

$a \equiv c \pmod{n}$

Can someone explain this? I think I am missing some simple idea here. Please help me understand this.

Winther
  • 24,478
Ankit
  • 63
  • 2
    $a\equiv b\pmod n$ means that $a-b$ is divisible by $n$. We have that $a-c = (a-b) + (b-c)$ so if both $a-b$ and $b-c$ are divisible by $n$ then so is $a-c$. In the modular arithmetics language this statement is just: $a\equiv b\pmod n$ and $b\equiv c \pmod n$ implies $a\equiv c\pmod n$. – Winther Oct 06 '15 at 06:59
  • 1
    Informally: $x\equiv y\pmod{n}$ means that $x$ and $y$ have the same remainder when divided by $n$. If $a$ and $b$ have the same remainder, and $b$ and $c$ have the same remainder, then $a$ and $c$ have the same remainder. – André Nicolas Oct 06 '15 at 07:01

1 Answers1

1

"Congruent mod $n$" is an equivalence relation. In particular, it is transitive. So, if $a\equiv b \mod n$ and $b\equiv c\mod n$, then $a \equiv c \mod n$. It's just like equality: If $a = b $ and $b=c$, then $a=c$.

ChocolateAndCheese
  • 1,542