modular arithmetic - Congruence modulo high power problem - Mathematics Stack Exchange
Congruence modulo Question
number theory - Proving congruent modulo - Mathematics Stack Exchange
notation - Why do we use "congruent to" instead of equal to? - Mathematics Stack Exchange
Videos
I think I understand the basics of the modulo function. Assuming modulo 3 when counting up you'd go 0 > 1 > 2 > 0 ...
But then I see this equation:
a ≡ b (mod n)
And have trouble understanding it. I'm pretty sure it means that a and b have a congruent relationship when a modulo function of n is applied to them. But I'm not sure if this is correct, and what a congruent relationship is.
Thanks!
Fermat's Little Theorem states that
If $n \in \mathbb N$, $p$ is a prime, and $p \not | \space \space n$ then $n^{p-1} \equiv1\pmod p$
If $n \in \mathbb N$, $p$ is a prime, then $n^p \equiv n \pmod p$
We have:
\begin{align} 2^{2014} = 2^{11\cdot183 + 1} \end{align}
Then, by the definition,
\begin{align} 2^{2014} & = 2^{11\cdot 183+1} \\ 2^{11\cdot 183+1} &\equiv 2^{183+1} \pmod {11}\\ \end{align}
\begin{align} 2^{183+1} &= 2^{184} \\ 2^{184} & = 2^{11\cdot {16} + 8} \\ 2^{11\cdot {16} + 8} &\equiv 2^{16+8} \pmod {11}\\ \end{align}
\begin{align} 2^{16+8} &= 2^{24} \\ 2^{24} & = 2^{11\cdot {2} + 2} \\ 2^{11\cdot {2} + 2} &\equiv 2^{2+2} \pmod {11}\\ \end{align}
We can easily see that $2^4 = 16$. Thus $2^{2014} \equiv 5 \pmod{11}$.
Alternatively, using the second part of the theorem,
We have:
\begin{align} 2^{2014}=2^{10\cdot 201 + 4} & \equiv 2^{4} \pmod {11} \\ \implies 2^{2014} \equiv 16 &\equiv 5 \pmod {11} \\ \end{align}
Notice that $2^{10\cdot 201}$ is equivalent to $0 \pmod {11}$. Thus, we can just eliminate it. I believe these two methods of solving the problem are equally correct. Hopefully you can see what I have manipulated to get an answer.
Let $\mathcal{U}_{11}$ be the set of integers coprime to $11$. Then, since $11$ is prime we have $$\mathcal{U}_{11}=\{1,2,3,4,5,6,7,8,9,10\}.$$
Let's write the first few powers of $2$ mod $11$, I'll represent the operation of multiplying by $2$ by arrows. Starting from $2^0$ we have
$$1 \rightarrow 2 \rightarrow 4 \rightarrow 8 \rightarrow 5 \rightarrow 10 \rightarrow 9 \rightarrow 7 \rightarrow 3 \rightarrow 6...$$ before repeating since we've seen every element in $\mathcal{U}_{11}$.
So, we see that after every multiple of ten entries in the sequence, we get back to $1$, that is $2^{10m}=1$. Let $m=201$, then $2^{2010}=1$. From here, we observe we just have another $4$ entries to go until we get to the $2014^{th}$ power. Just count $4$ along the sequence to give us $$2^{2014}=5.$$
If a is an integer, then a^2 is congruent to 0,1 or 4 modulo 5. Then wat about the case of 21. 21 is congruent to 1 modulo 5, but 21 is not a perfect square. Why is this?
In proving any relation involving congruences or such properties of congruences, I'll advise you to use the definition of congruence and convert the congruence to the division form and carry out the necessary calculations, i.e. use $n|a-b$ which means $a-b$ is divisible by $n$ instead of $a \equiv b \pmod n $
As for examples, I am working out your three problems.
- $$a \equiv a \pmod n , \forall a \in Z$$ So $n|a-a$ by definition and hence $$n|0$$ which is always true. Hence proved.
- $$ a \equiv b \pmod n \Rightarrow b \equiv a \pmod n$$ So $n|a-b$ by definition and hence $$n|b-a$$ or, $$b \equiv a \pmod n$$ Hence proved.
- $$a \equiv b \pmod n \land b \equiv c \pmod n \Rightarrow a \equiv c \pmod n$$ So $n|a-b$ and $n|b-c$ by definition and hence $$n|(a-b)+(b-c)$$ or, $$n|a-c$$ or, $$a \equiv c \pmod n$$ Hence proved.
$$\exists k\in\mathbb Z:a=b+kn$$ is indeed an equivalence relation.
$$a=a+0n,$$ $$a=b+kn\implies b=a-kn,$$ $$a=b+kn\land b=c+k'n\implies a=c+k'n+kn=c+k''n.$$
- I am a human being.
- You are a human being.
Therefore, I am you: right ? Well, as it turns out, the answer is no. It simply means that we belong to the same class. Likewise, $3\neq7$, but $3\equiv7\bmod4$.
I prefer to use the congruence exclusively (I view the remainder operation as a source of headache even though I realize that it is a necessary evil in computing).
But I use both equal ($=$) and congruent to ($\equiv$) signs together when processing a lengthy calculation in modular arithmetic. My freshman algebra students quickly catch on with my calculations like $$ 12^{3004}\equiv5^{3004}=5^{3000}\cdot 5^4=(5^6)^{500}\cdot 5^4\equiv 1^{500}\cdot5^4=25^2\equiv4^2=16\equiv2\pmod7. $$ IOW, I use $=$ when there is an equality of integers between the steps, and $\equiv$ when I mean a congruence. The power of laws obeyed by congruences is apparent. Checking/following the progress of the calculation is easier this way. Of course, using $\equiv$ all the way is correct also. The $\equiv$ is there as a reminder that in this step we do something that only results in a congruence.
As the students become acquainted with the language of residue class rings, I gradually stop making the distinction between $=$ and $\equiv$ as well as, clarity of context permitting, the distinction between $n$ and $\overline{n}$.
Thinking about what that would look like when done by somebody who is only familiar with binary mod makes me shudder.
That depends on your definition of the remainder, which in turn depends on a definition of 'integer division'.
It's quite easy for positive numbers: the result of division is the largest integer not exceeding the exact result. For example 5/8 = 0. Then the remainder is 5–8*(8/5) = 5–8*0 = 5.
For negative numbers, however, a problem appears with a meaning of 'the largest'. One can assume it is the value largest with respect to its absolute value, i.e. the result is rounded towards zero (some programming languages work this way); then the integer division (–5)/8 results in –0=0, and the remainder is –5.
Or one can take literally the largest value, in which case (–5)/8=–1 and then the remainder is 3.
A quick answer is that when we work with modulo n and you are using the following definition:
two numbers, namely a and b, are congruent modulo n <=> a%n = b%n
We have to consider the same criteria in order for them to be equal, and that is, to consider a remainder of the same sign as the divisor.
The long answer involves some group theory in there. It is not easy to sumarize in a few words, but can be simply explained, using the example you have provided along the way. First, we will consider the group of remainders modulo, that is, a set of posible positive remainders when a integer is divided by n. Through the perspective of the group, -3 and 5 are the same element, because -3 + 8 = 5.
P.D.: I advise you from reading that book if such definition was given, such vague definitions are misleading and not rigorous in mathematics. By the way, if you want a good book about number theory I recommend: H. Rosen, Kenneth, Elementary Number Theory, Fifth Edition, Pearson ISBN-0-321-26314-6