Question

How to prove it?

Answer 1

How to prove \(Z_n =<[d]>~~~iff~~~gcd(d,n)=1\)

Answer 2

@nerdguy2535

Answer 3

i think a double set inclusion should work here. Clearly \(\langle [d]\rangle \subseteq \mathbb Z_n\). We just need the other inclusion.

Answer 4

Since \(\langle [1]\rangle =\mathbb Z_n \) (i.e. \(\mathbb Z_n\) is cyclic), we just need to show that \([1]\in \langle [d]\rangle\). Then it follows that \(\mathbb Z_n\subseteq \langle [d]\rangle \).

Answer 5

To show that \([1]\in \langle [d]\rangle \), we need to show there exists an integer \(m\) such that: $$m[d]=[1].$$Can you think of a way to use the hypothesis that \(\gcd(d,n)=1\) to show the existence of such an m?

Answer 6

Why do we have to do that? for this way (-->), is it not that if \(\mathbb Z_n =\langle[d]\rangle \) means elements in d is in Z_n??

Answer 7

Ah, I didn't realize its an iff. I'm doing \(\Longleftarrow\) right now. Is \(\Longrightarrow \) the one you would rather tackle first?

Answer 8

either of them. I have to generalize the case in my attachment formally. We cannot "Notice" or "Observe" in our argument, right? :)

Answer 9

Right. The key to using the gcd condition is the following theorem:
$$\gcd(d,n)=1\iff \text{There exist }x,y\in \mathbb{Z}\text{ such that }dx+ny=1.$$

Answer 10

Have you seen this theorem before?

Answer 11

yes, but I don't see the link between generator d with it

Answer 12

I think you should play with that theorem some more then. The gcd(d,n) is very much related to what \(\langle [d]\rangle \) generates, and that theorem is pretty much the bridge that connects them.

Answer 13

This is what I did, but I go nowhere.
Suppose gcd (d,n ) = a, so that a|d and a|n and d = a a1 , n = a a2
that gives me d/a1= n/a2 --> d = \(\dfrac{a_1}{a_2}n\)

Answer 14

if [d] generate Z_n, then
1[d] = element in Z_n
2[d] = same as above
3[d]=
........
and we know that [d] = d (modn)

Answer 15

and replace d =a1/a2 n
I have 1d = a1/a2 * n
if I have \(\dfrac{a_2}{a_1} d= n\) then I can show this n does not belong to Z_n
so that gcd (d,n) must be 1

Answer 16

But it is ambiguous. :(

Answer 17

When working with \(\mathbb Z_n \), you don't want to have fractions flying around. So I don't think working with statements like \(d=\frac{a_1}{a_2}n\) are very helpful =/

Answer 18

It should always be about integers, or equivalence classes of integers.

Answer 19

yes,

Answer 20

If \(\langle[d]\rangle=\mathbb Z_n\), then for all \([y]\in \mathbb Z _n\), there exists an integer \(x\) such that \(x[d]=[y].\) In particular, there exists an integer \(x_0 \) such that \(x_0 [d]=[1]\). Can you use this to find a linear combination of d and n that equals 1?

Answer 21

We have theorem like:
if [d] generates Zn , order of [d], namely k, then gcd(k, n) =1
does it help us?

Answer 22

I think you might be misquoting that theorem >.< as written its not true. For example, take \([5]\in \mathbb Z_6\). [5] generates the group, so the order of [5] is 6, and the gcd(6,6)=6, not 1.

Answer 23

http://www.youtube.com/watch?v=atKkbR2cUt4

Answer 24

What the youtube theorem says is "If [d] generates Zn, then k[d] also generates Zn if and only of gcd(k,n)=1". That statement has nothing to do with the order of [d].

Answer 25

:( I spent 2 days on this problem, make a lot of short research, watch a lot of youtube tutoring but get nothing. :(

Answer 26

:(

Answer 27

All the information you need is in this thread now (for the most part). You just have to put it together.

Answer 28

How?

Answer 29

Its all in the theorem. $$\gcd(d,n)=1\iff \text{there exists}x,y\in \mathbb Z\text{ such that }dx+ny=1.$$

Answer 30

Because: $$dx+ny=1\iff [xd]=[1]\iff x[d]=[1]\iff [1]\in \langle [d]\rangle$$

Answer 31

then?

Answer 32

\([1]\in \langle [d]\rangle \iff \langle [1]\rangle \subseteq \langle [d]\rangle\iff \mathbb Z_n\subseteq \langle [d]\rangle \iff \mathbb Z_n =\langle [d]\rangle .\)

Answer 33

oh, I see, you prove if gcd (d, n) =1 then Z_n = <[d]>
the leftover is backward, right?

Answer 34

right right.

Answer 35

I gave up. It's 1:19 am here. I miss my bed. hihihi....
Thanks for your time.
Please, forgive me for my impoliteness. I am so tired.

Answer 36

no worries.