Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What operations can I perform on congruences to transform the modulo n? Specifically, in a formula such as Fermat's Little Theorem (or a generalization) $b^{p-1}$ $\equiv$ $1$ mod $p$

  1. What operations can one perform on the mod $p$ part?
  2. How could I manipulate this congruence: $7^{24}$ $\equiv$ $1$ mod $25$ to have a mod $10$?
share|improve this question
1  
This article will suit your needs –  Bhargav Sep 16 '12 at 5:18
    
Could you write a few sentences explaining? I cannot answer my questions from reading that article. –  CodeKingPlusPlus Sep 17 '12 at 1:43
add comment

2 Answers

up vote 2 down vote accepted

You ask three questions. Only the third is sufficiently focussed to admit an answer. If $a\equiv b\pmod{cd}$, then $a\equiv b\pmod{c}$. It follows then from $7^{24}\equiv1\pmod{25}$, that $7^{24}\equiv1\pmod{5}$.

Moreover, $7\equiv1\pmod2$, so $7^{24}\equiv1^{24}\equiv1\pmod2$.

So $7^{24}-1$ is a multiple of both 5 and 2, thus of 10, so $7^{24}\equiv1\pmod{10}$.

share|improve this answer
add comment

You can probably answer your own questions.

$a\equiv b \bmod c$ means that $a = b+nc$ for some integer $n$.

So the operations that you can do in modular arithmetic are all really consequences of operations you can do to the equality.

For example, can I add $1$ to both sides of a congruence? The answer is yes because we may add $1$ to both sides of the equality $a=b+nc$ and get $a+1 = (b+1)+nc$ ... which, in congruence notation, means $a+1 \equiv b+1 \bmod c$.

Can I multiply both sides of a congruence by $3$? The answer is yes because we may multiply both sides of the equality $a=b+nc$ by $3$ and get $3a = 3b+3nc = 3b + mc$ (where $m = 3n$ is just some other integer).

In congruence notation this means $3a \equiv 3b \bmod c$, or it could even mean $3a \equiv 3b \bmod 3c$. So when it comes to multiplication we really have two types, one effecting the modulus and one not.

The main problem occurs with division in modular arithmetic since division usually leads to fractions and modular arithmetic is something about integers only. You might like to investigate when you can "cancel" things. For example can I cancel by $3$ in $3a \equiv 3b \bmod 3c$ to get $a\equiv b \bmod c$? How about in $3a\equiv 3b \bmod c$? Does it matter what $c$ is?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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