Question

compute \(2^{2r}\) (mod 3), for all positive integers r.
Please, check

Answer 1

\(2^{2r}=4^r\) and \(4\equiv 1(mod3)\) so that \(2^{2r}\equiv 1(mod3)\)
Am I right?

Answer 2

seems fair to me.

Answer 3

Please, help on this:
Let t be an integers, and let n be a positive integer. Prove that:
\[Z_n= \{[0],[1],....,[n-1]\}=\{[t],[t+1],....,[t+(n-1)]\}\]
How to start?

Answer 4

do the square brackets mean anything special?

Answer 5

That is class in modulo n

Answer 6

just terminology, like in Z_5, 4+1= 0, but we use [4]+[1]=0

Answer 7

Z mod n is defined to be the set of classes ..... got it

Answer 8

im thinking the proof has something to do with the cyclic nature of the group

Answer 9

by convention, we organize it 0 to n-1 but what we name the elements is of little consequence to the properties of the group

Answer 10

since t is some element within a class of Z mod n, and the name of the set can be referencned by any element of the set ... something along those lines

Answer 11

We don't have it, we need to prove it. From the beginning, t is just an integer in Z

Answer 12

just an idea, not to sure how to put it into 'proper' stuff tho :) but for example

say t = 5 mod 8

the set Z8 = {5,6,7,8,9,10,11,12} = {5,6,7,0,1,2,3,4} = {0,1,2,3,4,5,6,7}

Answer 13

We have elements in Z_n is the middle term of the expression. I mean \(Z_n= \{[0],[1],....,[n-1]\}\)
and we need to prove that if n|t, then the remainder will be \(\{[t],[t+1],....,[t+(n-1)]\}\)

Answer 14

Can we prove the group of the middle one isomophic to the group of the right one?

Answer 15

thats along the lines of what im thinking yes. simply by showing the t is congruent to some class, [x] in Z mod n. and by definition t+1 is congruent to the class [x+1] etc

Answer 16

in my example:

5 = 13 mod 8 just as well as 13 = 5 mod 8 because of symetry might be the proper name of for it

Answer 17

Continue, please. We didn't reach somewhere yet. :)

Answer 18

since Z mod n is cyclic, and t = x mod n, then for some k, t+k = x+k = 0 mod n, but without my texts handy a proper write up wouldnt be possible for me

Answer 19

but my proof attempt would be along those thoughts

Answer 20

I'm not sure how much about Z (mod n) is standard knowledge, so some of the things I post might seem trivial.

Claim 1: Let $$0\le i \le n-1.$$ If $$t+i=qn+r$$ for some integers q and r with: $$0\le r \le n-1,$$ then: $$[t+i]=[r].$$
Proof: If t+i=qn+r, then (t+i)-r=qn, a multiple of n. This is exactly the definition of what it means to be congruent mod n.

Answer 21

Claim 2:
\[\left\{ [t],[t+1], \ldots , [t+(n-1)] \right\}\subset \left\{ [0],[1], \ldots , [n-1] \right\}\]
Proof: It turns out any integer b can be written as b = qn+r with $$0\le r\le n-1.$$This is the division algorithm. So for any i, [t+i]=[r] for some r between 0 and n-1.

Now all thats left to do is show that each [t+i] is distinct. That is...

Answer 22

Claim 3: Let $$0\le i,j \le n-1, i\ne j.$$ Then $$[t+i]\ne [t+j].$$
Proof: Either a proof by contradiction or the contrapositive will work here. I'll work by contradiction. If [t+i]=[t+j], then [t] + [i] = [t] + [j], whence [i] = [j]. This means i-j = qn for some q in Z. However, since both i and j are integers between 0 and n-1, their difference is smaller than n, i.e: $$|i-j|<n.$$ Therefore, if i-j=qn, q must be 0, and we see that i-j=0 which implies i=j, a contradiction.

Answer 23

Now that we know all the [t+i] are distinct, its clear that:\[\left\{ [t],[t+1],\ldots , [t+(n-1)] \right\}=\left\{ [0],[1],\ldots , [n-1] \right\}\]since one is contained in the other, and they both have the same number of elements.

Answer 24

How weird would it be to do induction.
So we can prove for all natural t we have
\[\left\{ [t],[t+1],\ldots , [t+(n-1)] \right\}=\left\{ [0],[1],\ldots , [n-1] \right\} \]

---
Clearly it works for t=0
And for t=1, we have [0] in that one set but not in the other or at least we have him in disguise in the other group as [n].

So for assume for some integer t=k we have \[\left\{ [k],[k+1],\ldots , [k+(n-1)] \right\}=\left\{ [0],[1],\ldots , [n-1] \right\} \]
Now we want to show it is true for t=k+1
\[\left\{ [k+1],[k+2],\ldots , [k+n)] \right\}=\left\{ [0],[1],\ldots , [n-1] \right\} \]

So only element that wasn't in set Pk that in P(k+1) is [k+n] and the only element that is in P(k+1) that is not in Pk is [k].
But [k] is equivalent to [n+k].
So that meants \[\left\{ [k],[k+1],\ldots , [k+(n-1)] \right\}=\left\{ [k+1],[k+2],\ldots , [k+n)] \right\}=\left\{ [0],[1],\ldots , [n-1] \right\} \]