Mixing
How to prove that the order of $x$ modulo $N$ satisfies $r leq N$?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I'm rather new to number theory and don't have any knowledge in group theory at all. How can I prove that the least positive integer $r$ such that $x^r=1 (mod N) $ satisfies $r leq N$?
My thoughts on this problem:
In the definition of order modulo $N$ it is stated that $x<N$ and $gcd(x,N)=1$.
This fact allows us (using $gcd$ representation theorem) to state that there exist integers $a,b$ such that $ax+bN=1$. I think I have to use this somehow, but I'm stuck on this step. Can I please get help?
UPD: Thanks to everybody who helped me, the proofs are really elegant and smart!
number-theory elementary-number-theory modular-arithmetic
asked Jul 19 at 13:14
Aleksandr Berezutskii
32
add a comment |Â
up vote
0
down vote
favorite
I'm rather new to number theory and don't have any knowledge in group theory at all. How can I prove that the least positive integer $r$ such that $x^r=1 (mod N) $ satisfies $r leq N$?
My thoughts on this problem:
In the definition of order modulo $N$ it is stated that $x<N$ and $gcd(x,N)=1$.
This fact allows us (using $gcd$ representation theorem) to state that there exist integers $a,b$ such that $ax+bN=1$. I think I have to use this somehow, but I'm stuck on this step. Can I please get help?
UPD: Thanks to everybody who helped me, the proofs are really elegant and smart!
number-theory elementary-number-theory modular-arithmetic
asked Jul 19 at 13:14
Aleksandr Berezutskii
32
You need the condition that a and n be coprime, otherwise the question is formally nonsense. Keep in mind that powers of an element in a group form a periodic sequence, and the period is the order of the elements. Furthermore, inside a period, any two powers are different. As there are less then N different powers of the element a (since 0 is not a power), we are done.
– A. Pongrácz
Jul 19 at 13:20
Do You mean $x$ and $N$ are coprime?
– Aleksandr Berezutskii
Jul 19 at 13:25
Yes, indeed. Sorry.
– A. Pongrácz
Jul 19 at 13:26
Thank You! Your comment helped me to understand the fact that order modulo $N$ basically gives the number of different residues modulo $N$ that exist for different powers of $x$
– Aleksandr Berezutskii
Jul 19 at 13:59
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I'm rather new to number theory and don't have any knowledge in group theory at all. How can I prove that the least positive integer $r$ such that $x^r=1 (mod N) $ satisfies $r leq N$?
My thoughts on this problem:
In the definition of order modulo $N$ it is stated that $x<N$ and $gcd(x,N)=1$.
This fact allows us (using $gcd$ representation theorem) to state that there exist integers $a,b$ such that $ax+bN=1$. I think I have to use this somehow, but I'm stuck on this step. Can I please get help?
UPD: Thanks to everybody who helped me, the proofs are really elegant and smart!
number-theory elementary-number-theory modular-arithmetic
asked Jul 19 at 13:14
Aleksandr Berezutskii
32
I'm rather new to number theory and don't have any knowledge in group theory at all. How can I prove that the least positive integer $r$ such that $x^r=1 (mod N) $ satisfies $r leq N$?
My thoughts on this problem:
In the definition of order modulo $N$ it is stated that $x<N$ and $gcd(x,N)=1$.
This fact allows us (using $gcd$ representation theorem) to state that there exist integers $a,b$ such that $ax+bN=1$. I think I have to use this somehow, but I'm stuck on this step. Can I please get help?
UPD: Thanks to everybody who helped me, the proofs are really elegant and smart!
number-theory elementary-number-theory modular-arithmetic
asked Jul 19 at 13:14
Aleksandr Berezutskii
32
edited Jul 19 at 14:05
asked Jul 19 at 13:14
Aleksandr Berezutskii
32
asked Jul 19 at 13:14
Aleksandr Berezutskii
32
asked Jul 19 at 13:14
Aleksandr Berezutskii
32
32
You need the condition that a and n be coprime, otherwise the question is formally nonsense. Keep in mind that powers of an element in a group form a periodic sequence, and the period is the order of the elements. Furthermore, inside a period, any two powers are different. As there are less then N different powers of the element a (since 0 is not a power), we are done.
– A. Pongrácz
Jul 19 at 13:20
Do You mean $x$ and $N$ are coprime?
– Aleksandr Berezutskii
Jul 19 at 13:25
Yes, indeed. Sorry.
– A. Pongrácz
Jul 19 at 13:26
Thank You! Your comment helped me to understand the fact that order modulo $N$ basically gives the number of different residues modulo $N$ that exist for different powers of $x$
– Aleksandr Berezutskii
Jul 19 at 13:59
add a comment |Â
You need the condition that a and n be coprime, otherwise the question is formally nonsense. Keep in mind that powers of an element in a group form a periodic sequence, and the period is the order of the elements. Furthermore, inside a period, any two powers are different. As there are less then N different powers of the element a (since 0 is not a power), we are done.
– A. Pongrácz
Jul 19 at 13:20
Do You mean $x$ and $N$ are coprime?
– Aleksandr Berezutskii
Jul 19 at 13:25
Yes, indeed. Sorry.
– A. Pongrácz
Jul 19 at 13:26
Thank You! Your comment helped me to understand the fact that order modulo $N$ basically gives the number of different residues modulo $N$ that exist for different powers of $x$
– Aleksandr Berezutskii
Jul 19 at 13:59
You need the condition that a and n be coprime, otherwise the question is formally nonsense. Keep in mind that powers of an element in a group form a periodic sequence, and the period is the order of the elements. Furthermore, inside a period, any two powers are different. As there are less then N different powers of the element a (since 0 is not a power), we are done.
– A. Pongrácz
Jul 19 at 13:20
You need the condition that a and n be coprime, otherwise the question is formally nonsense. Keep in mind that powers of an element in a group form a periodic sequence, and the period is the order of the elements. Furthermore, inside a period, any two powers are different. As there are less then N different powers of the element a (since 0 is not a power), we are done.
– A. Pongrácz
Jul 19 at 13:20
Do You mean $x$ and $N$ are coprime?
– Aleksandr Berezutskii
Jul 19 at 13:25
Do You mean $x$ and $N$ are coprime?
– Aleksandr Berezutskii
Jul 19 at 13:25
Yes, indeed. Sorry.
– A. Pongrácz
Jul 19 at 13:26
Yes, indeed. Sorry.
– A. Pongrácz
Jul 19 at 13:26
Thank You! Your comment helped me to understand the fact that order modulo $N$ basically gives the number of different residues modulo $N$ that exist for different powers of $x$
– Aleksandr Berezutskii
Jul 19 at 13:59
Thank You! Your comment helped me to understand the fact that order modulo $N$ basically gives the number of different residues modulo $N$ that exist for different powers of $x$
– Aleksandr Berezutskii
Jul 19 at 13:59
add a comment |Â
4 Answers
4
active
oldest
votes
up vote
0
down vote
accepted
Yes, indeed you need that $gcd(x,N)=1$, because otherwise the statement is not true. Look e.g. at $2^requiv 1pmod 4$, which is only true for $r=0$ but not for any positive integer. So I will assume $gcd(x,N)=1$ in the following.
Look at the list
$$x^0,x^1,x^2,...,x^N-1,x^N$$
modulo $N$. This can give you at most $N$ different numbers, namely $0,...,N-1$. But the list has length $N+1$, so some number must ocure at least twice (pidgeonhole principle).
So, let's say $x^nequiv x^mpmod N$ with $n>m$. Maybe you already know that for $gcd(x,N)=1$ there is a unique multiplicative inverse $x^-1$ so that $xcdot x^-1equiv 1pmod N$. We multiply $x^-m:=(x^-1)^m$ to both sides:
beginalign
x^n&equiv x^mpmod N &|cdot x^-m \
x^ncdot x^-m&equiv x^mcdot x^-mpmod N \
x^n-m&equiv 1pmod N \
endalign
Since $n,mle N$ and $n>m$ we have that $r:=n-mle N$ (actually $r<N$).
answered Jul 19 at 13:28
M. Winter
17.7k62764
add a comment |Â
up vote
0
down vote
Draw $N$ points numbered $v_1, cdots, v_N$ on a circle. Draw an arrow from $v_i$ to $v_j$ if $v_j equiv v_ix mod N$. Now if you start following the arrows from $v_1$ (i.e start from $v_1$, then go to $v_j$ such that there's an arrow from $v_1$ to $v_j$ etc).
If $gcd(x,N) neq 1$, then you would end up in a rho shape (eventually land up in a circle with a tail). But otherwise $x^-1 mod N$ exists, so you must end up in a circle.
Try to find out why this happens by actually doing it with a pen and paper for $x = 2, N = 5$ and I think you should be able to understand why this is true (hint: use pigeon-hole principle and the existence of inverse)
answered Jul 19 at 13:23
alxchen
402320
add a comment |Â
up vote
0
down vote
Consider the residues of $x^0,x^1,x^2,...,x^N$ modulo $N$. (Take for example, the least positive residue.)
Then, there are $N+1$ residues listed above but there are only $N$ distinct residues modulo $N$.
So $x^iequiv x^j (textrmmod N)$.
Here it may be tempting to say $x^i-jequiv 1 (textrmmod N)$ but here you do need the condition that $x$ and $N$ are coprime because in general this is not true.
(e.g. $6^2equiv 6(textrmmod 10)$ but clearly $6notequiv 1(textrmmod 10)$)
And so if $x$ and $N$ are coprime, $x^j$ and $N$ are coprime as well so we can "cancel out" $x^j$ which is the equivalent of multiplying out about the inverse of $x^j$.
answered Jul 19 at 13:29
daruma
900512
add a comment |Â
up vote
0
down vote
Suppose there exists $m in Bbb Z^+$ such that $x^mequiv 1mod N.$ Let $n$ be the least such $m.$
(1). If $1leq a<bleq n$ then $x^anot equiv x^b mod N.$ Proof: By contradiction: If $x^aequiv x^b$ let $m=a+(n-b).$ Then $$x^mequiv x^a+(n-b)equiv x^a x^n-bequiv$$ $$equiv x^bx^n-b=x^b+n-bequiv x^nequiv 1$$ but $1leq aleq a+(n-b)=m=n-(b-a)<n,$ so $1leq m<n$ so by def'n of $n$ we have $x^mnot equiv 1,$ a contradiction.
(2). For $1leq aleq n$ let $1leq f(a)leq N$ such that $x^aequiv f(a) mod N.$ By (1), the set $S=f(a): 1leq aleq n$ has exactly $n$ members. But $S$ is a subset of the $N$-member set $y:1leq yleq N $ so $nleq N.$
answered Jul 20 at 6:10
DanielWainfleet
31.7k31643
(1) implies that the function $f$ is 1-to-1. Without this we could only say that $S$ has at most $n$ members, which would be of no use.
– DanielWainfleet
Jul 20 at 6:18
I tried to answer without the topic of multiplicative inverses $mod N$.
– DanielWainfleet
Jul 20 at 6:24
add a comment |Â
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
Yes, indeed you need that $gcd(x,N)=1$, because otherwise the statement is not true. Look e.g. at $2^requiv 1pmod 4$, which is only true for $r=0$ but not for any positive integer. So I will assume $gcd(x,N)=1$ in the following.
Look at the list
$$x^0,x^1,x^2,...,x^N-1,x^N$$
modulo $N$. This can give you at most $N$ different numbers, namely $0,...,N-1$. But the list has length $N+1$, so some number must ocure at least twice (pidgeonhole principle).
So, let's say $x^nequiv x^mpmod N$ with $n>m$. Maybe you already know that for $gcd(x,N)=1$ there is a unique multiplicative inverse $x^-1$ so that $xcdot x^-1equiv 1pmod N$. We multiply $x^-m:=(x^-1)^m$ to both sides:
beginalign
x^n&equiv x^mpmod N &|cdot x^-m \
x^ncdot x^-m&equiv x^mcdot x^-mpmod N \
x^n-m&equiv 1pmod N \
endalign
Since $n,mle N$ and $n>m$ we have that $r:=n-mle N$ (actually $r<N$).
answered Jul 19 at 13:28
M. Winter
17.7k62764
add a comment |Â
up vote
0
down vote
accepted
Yes, indeed you need that $gcd(x,N)=1$, because otherwise the statement is not true. Look e.g. at $2^requiv 1pmod 4$, which is only true for $r=0$ but not for any positive integer. So I will assume $gcd(x,N)=1$ in the following.
Look at the list
$$x^0,x^1,x^2,...,x^N-1,x^N$$
modulo $N$. This can give you at most $N$ different numbers, namely $0,...,N-1$. But the list has length $N+1$, so some number must ocure at least twice (pidgeonhole principle).
So, let's say $x^nequiv x^mpmod N$ with $n>m$. Maybe you already know that for $gcd(x,N)=1$ there is a unique multiplicative inverse $x^-1$ so that $xcdot x^-1equiv 1pmod N$. We multiply $x^-m:=(x^-1)^m$ to both sides:
beginalign
x^n&equiv x^mpmod N &|cdot x^-m \
x^ncdot x^-m&equiv x^mcdot x^-mpmod N \
x^n-m&equiv 1pmod N \
endalign
Since $n,mle N$ and $n>m$ we have that $r:=n-mle N$ (actually $r<N$).
answered Jul 19 at 13:28
M. Winter
17.7k62764
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
Yes, indeed you need that $gcd(x,N)=1$, because otherwise the statement is not true. Look e.g. at $2^requiv 1pmod 4$, which is only true for $r=0$ but not for any positive integer. So I will assume $gcd(x,N)=1$ in the following.
Look at the list
$$x^0,x^1,x^2,...,x^N-1,x^N$$
modulo $N$. This can give you at most $N$ different numbers, namely $0,...,N-1$. But the list has length $N+1$, so some number must ocure at least twice (pidgeonhole principle).
So, let's say $x^nequiv x^mpmod N$ with $n>m$. Maybe you already know that for $gcd(x,N)=1$ there is a unique multiplicative inverse $x^-1$ so that $xcdot x^-1equiv 1pmod N$. We multiply $x^-m:=(x^-1)^m$ to both sides:
beginalign
x^n&equiv x^mpmod N &|cdot x^-m \
x^ncdot x^-m&equiv x^mcdot x^-mpmod N \
x^n-m&equiv 1pmod N \
endalign
Since $n,mle N$ and $n>m$ we have that $r:=n-mle N$ (actually $r<N$).
answered Jul 19 at 13:28
M. Winter
17.7k62764
Yes, indeed you need that $gcd(x,N)=1$, because otherwise the statement is not true. Look e.g. at $2^requiv 1pmod 4$, which is only true for $r=0$ but not for any positive integer. So I will assume $gcd(x,N)=1$ in the following.
Look at the list
$$x^0,x^1,x^2,...,x^N-1,x^N$$
modulo $N$. This can give you at most $N$ different numbers, namely $0,...,N-1$. But the list has length $N+1$, so some number must ocure at least twice (pidgeonhole principle).
So, let's say $x^nequiv x^mpmod N$ with $n>m$. Maybe you already know that for $gcd(x,N)=1$ there is a unique multiplicative inverse $x^-1$ so that $xcdot x^-1equiv 1pmod N$. We multiply $x^-m:=(x^-1)^m$ to both sides:
beginalign
x^n&equiv x^mpmod N &|cdot x^-m \
x^ncdot x^-m&equiv x^mcdot x^-mpmod N \
x^n-m&equiv 1pmod N \
endalign
Since $n,mle N$ and $n>m$ we have that $r:=n-mle N$ (actually $r<N$).
answered Jul 19 at 13:28
M. Winter
17.7k62764
answered Jul 19 at 13:28
M. Winter
17.7k62764
answered Jul 19 at 13:28
M. Winter
17.7k62764
answered Jul 19 at 13:28
M. Winter
17.7k62764
17.7k62764
add a comment |Â
add a comment |Â
up vote
0
down vote
Draw $N$ points numbered $v_1, cdots, v_N$ on a circle. Draw an arrow from $v_i$ to $v_j$ if $v_j equiv v_ix mod N$. Now if you start following the arrows from $v_1$ (i.e start from $v_1$, then go to $v_j$ such that there's an arrow from $v_1$ to $v_j$ etc).
If $gcd(x,N) neq 1$, then you would end up in a rho shape (eventually land up in a circle with a tail). But otherwise $x^-1 mod N$ exists, so you must end up in a circle.
Try to find out why this happens by actually doing it with a pen and paper for $x = 2, N = 5$ and I think you should be able to understand why this is true (hint: use pigeon-hole principle and the existence of inverse)
answered Jul 19 at 13:23
alxchen
402320
add a comment |Â
up vote
0
down vote
Draw $N$ points numbered $v_1, cdots, v_N$ on a circle. Draw an arrow from $v_i$ to $v_j$ if $v_j equiv v_ix mod N$. Now if you start following the arrows from $v_1$ (i.e start from $v_1$, then go to $v_j$ such that there's an arrow from $v_1$ to $v_j$ etc).
If $gcd(x,N) neq 1$, then you would end up in a rho shape (eventually land up in a circle with a tail). But otherwise $x^-1 mod N$ exists, so you must end up in a circle.
Try to find out why this happens by actually doing it with a pen and paper for $x = 2, N = 5$ and I think you should be able to understand why this is true (hint: use pigeon-hole principle and the existence of inverse)
answered Jul 19 at 13:23
alxchen
402320
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Draw $N$ points numbered $v_1, cdots, v_N$ on a circle. Draw an arrow from $v_i$ to $v_j$ if $v_j equiv v_ix mod N$. Now if you start following the arrows from $v_1$ (i.e start from $v_1$, then go to $v_j$ such that there's an arrow from $v_1$ to $v_j$ etc).
If $gcd(x,N) neq 1$, then you would end up in a rho shape (eventually land up in a circle with a tail). But otherwise $x^-1 mod N$ exists, so you must end up in a circle.
Try to find out why this happens by actually doing it with a pen and paper for $x = 2, N = 5$ and I think you should be able to understand why this is true (hint: use pigeon-hole principle and the existence of inverse)
answered Jul 19 at 13:23
alxchen
402320
Draw $N$ points numbered $v_1, cdots, v_N$ on a circle. Draw an arrow from $v_i$ to $v_j$ if $v_j equiv v_ix mod N$. Now if you start following the arrows from $v_1$ (i.e start from $v_1$, then go to $v_j$ such that there's an arrow from $v_1$ to $v_j$ etc).
If $gcd(x,N) neq 1$, then you would end up in a rho shape (eventually land up in a circle with a tail). But otherwise $x^-1 mod N$ exists, so you must end up in a circle.
Try to find out why this happens by actually doing it with a pen and paper for $x = 2, N = 5$ and I think you should be able to understand why this is true (hint: use pigeon-hole principle and the existence of inverse)
answered Jul 19 at 13:23
alxchen
402320
answered Jul 19 at 13:23
alxchen
402320
answered Jul 19 at 13:23
alxchen
402320
answered Jul 19 at 13:23
alxchen
402320
402320
add a comment |Â
add a comment |Â
up vote
0
down vote
Consider the residues of $x^0,x^1,x^2,...,x^N$ modulo $N$. (Take for example, the least positive residue.)
Then, there are $N+1$ residues listed above but there are only $N$ distinct residues modulo $N$.
So $x^iequiv x^j (textrmmod N)$.
Here it may be tempting to say $x^i-jequiv 1 (textrmmod N)$ but here you do need the condition that $x$ and $N$ are coprime because in general this is not true.
(e.g. $6^2equiv 6(textrmmod 10)$ but clearly $6notequiv 1(textrmmod 10)$)
And so if $x$ and $N$ are coprime, $x^j$ and $N$ are coprime as well so we can "cancel out" $x^j$ which is the equivalent of multiplying out about the inverse of $x^j$.
answered Jul 19 at 13:29
daruma
900512
add a comment |Â
up vote
0
down vote
Consider the residues of $x^0,x^1,x^2,...,x^N$ modulo $N$. (Take for example, the least positive residue.)
Then, there are $N+1$ residues listed above but there are only $N$ distinct residues modulo $N$.
So $x^iequiv x^j (textrmmod N)$.
Here it may be tempting to say $x^i-jequiv 1 (textrmmod N)$ but here you do need the condition that $x$ and $N$ are coprime because in general this is not true.
(e.g. $6^2equiv 6(textrmmod 10)$ but clearly $6notequiv 1(textrmmod 10)$)
And so if $x$ and $N$ are coprime, $x^j$ and $N$ are coprime as well so we can "cancel out" $x^j$ which is the equivalent of multiplying out about the inverse of $x^j$.
answered Jul 19 at 13:29
daruma
900512
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Consider the residues of $x^0,x^1,x^2,...,x^N$ modulo $N$. (Take for example, the least positive residue.)
Then, there are $N+1$ residues listed above but there are only $N$ distinct residues modulo $N$.
So $x^iequiv x^j (textrmmod N)$.
Here it may be tempting to say $x^i-jequiv 1 (textrmmod N)$ but here you do need the condition that $x$ and $N$ are coprime because in general this is not true.
(e.g. $6^2equiv 6(textrmmod 10)$ but clearly $6notequiv 1(textrmmod 10)$)
And so if $x$ and $N$ are coprime, $x^j$ and $N$ are coprime as well so we can "cancel out" $x^j$ which is the equivalent of multiplying out about the inverse of $x^j$.
answered Jul 19 at 13:29
daruma
900512
Consider the residues of $x^0,x^1,x^2,...,x^N$ modulo $N$. (Take for example, the least positive residue.)
Then, there are $N+1$ residues listed above but there are only $N$ distinct residues modulo $N$.
So $x^iequiv x^j (textrmmod N)$.
Here it may be tempting to say $x^i-jequiv 1 (textrmmod N)$ but here you do need the condition that $x$ and $N$ are coprime because in general this is not true.
(e.g. $6^2equiv 6(textrmmod 10)$ but clearly $6notequiv 1(textrmmod 10)$)
And so if $x$ and $N$ are coprime, $x^j$ and $N$ are coprime as well so we can "cancel out" $x^j$ which is the equivalent of multiplying out about the inverse of $x^j$.
answered Jul 19 at 13:29
daruma
900512
answered Jul 19 at 13:29
daruma
900512
answered Jul 19 at 13:29
daruma
900512
answered Jul 19 at 13:29
daruma
900512
900512
add a comment |Â
add a comment |Â
up vote
0
down vote
Suppose there exists $m in Bbb Z^+$ such that $x^mequiv 1mod N.$ Let $n$ be the least such $m.$
(1). If $1leq a<bleq n$ then $x^anot equiv x^b mod N.$ Proof: By contradiction: If $x^aequiv x^b$ let $m=a+(n-b).$ Then $$x^mequiv x^a+(n-b)equiv x^a x^n-bequiv$$ $$equiv x^bx^n-b=x^b+n-bequiv x^nequiv 1$$ but $1leq aleq a+(n-b)=m=n-(b-a)<n,$ so $1leq m<n$ so by def'n of $n$ we have $x^mnot equiv 1,$ a contradiction.
(2). For $1leq aleq n$ let $1leq f(a)leq N$ such that $x^aequiv f(a) mod N.$ By (1), the set $S=f(a): 1leq aleq n$ has exactly $n$ members. But $S$ is a subset of the $N$-member set $y:1leq yleq N $ so $nleq N.$
answered Jul 20 at 6:10
DanielWainfleet
31.7k31643
(1) implies that the function $f$ is 1-to-1. Without this we could only say that $S$ has at most $n$ members, which would be of no use.
– DanielWainfleet
Jul 20 at 6:18
I tried to answer without the topic of multiplicative inverses $mod N$.
– DanielWainfleet
Jul 20 at 6:24
add a comment |Â
up vote
0
down vote
Suppose there exists $m in Bbb Z^+$ such that $x^mequiv 1mod N.$ Let $n$ be the least such $m.$
(1). If $1leq a<bleq n$ then $x^anot equiv x^b mod N.$ Proof: By contradiction: If $x^aequiv x^b$ let $m=a+(n-b).$ Then $$x^mequiv x^a+(n-b)equiv x^a x^n-bequiv$$ $$equiv x^bx^n-b=x^b+n-bequiv x^nequiv 1$$ but $1leq aleq a+(n-b)=m=n-(b-a)<n,$ so $1leq m<n$ so by def'n of $n$ we have $x^mnot equiv 1,$ a contradiction.
(2). For $1leq aleq n$ let $1leq f(a)leq N$ such that $x^aequiv f(a) mod N.$ By (1), the set $S=f(a): 1leq aleq n$ has exactly $n$ members. But $S$ is a subset of the $N$-member set $y:1leq yleq N $ so $nleq N.$
answered Jul 20 at 6:10
DanielWainfleet
31.7k31643
(1) implies that the function $f$ is 1-to-1. Without this we could only say that $S$ has at most $n$ members, which would be of no use.
– DanielWainfleet
Jul 20 at 6:18
I tried to answer without the topic of multiplicative inverses $mod N$.
– DanielWainfleet
Jul 20 at 6:24
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Suppose there exists $m in Bbb Z^+$ such that $x^mequiv 1mod N.$ Let $n$ be the least such $m.$
(1). If $1leq a<bleq n$ then $x^anot equiv x^b mod N.$ Proof: By contradiction: If $x^aequiv x^b$ let $m=a+(n-b).$ Then $$x^mequiv x^a+(n-b)equiv x^a x^n-bequiv$$ $$equiv x^bx^n-b=x^b+n-bequiv x^nequiv 1$$ but $1leq aleq a+(n-b)=m=n-(b-a)<n,$ so $1leq m<n$ so by def'n of $n$ we have $x^mnot equiv 1,$ a contradiction.
(2). For $1leq aleq n$ let $1leq f(a)leq N$ such that $x^aequiv f(a) mod N.$ By (1), the set $S=f(a): 1leq aleq n$ has exactly $n$ members. But $S$ is a subset of the $N$-member set $y:1leq yleq N $ so $nleq N.$
answered Jul 20 at 6:10
DanielWainfleet
31.7k31643
Suppose there exists $m in Bbb Z^+$ such that $x^mequiv 1mod N.$ Let $n$ be the least such $m.$
(1). If $1leq a<bleq n$ then $x^anot equiv x^b mod N.$ Proof: By contradiction: If $x^aequiv x^b$ let $m=a+(n-b).$ Then $$x^mequiv x^a+(n-b)equiv x^a x^n-bequiv$$ $$equiv x^bx^n-b=x^b+n-bequiv x^nequiv 1$$ but $1leq aleq a+(n-b)=m=n-(b-a)<n,$ so $1leq m<n$ so by def'n of $n$ we have $x^mnot equiv 1,$ a contradiction.
(2). For $1leq aleq n$ let $1leq f(a)leq N$ such that $x^aequiv f(a) mod N.$ By (1), the set $S=f(a): 1leq aleq n$ has exactly $n$ members. But $S$ is a subset of the $N$-member set $y:1leq yleq N $ so $nleq N.$
answered Jul 20 at 6:10
DanielWainfleet
31.7k31643
edited Jul 20 at 6:15
answered Jul 20 at 6:10
DanielWainfleet
31.7k31643
answered Jul 20 at 6:10
DanielWainfleet
31.7k31643
answered Jul 20 at 6:10
DanielWainfleet
31.7k31643
31.7k31643
(1) implies that the function $f$ is 1-to-1. Without this we could only say that $S$ has at most $n$ members, which would be of no use.
– DanielWainfleet
Jul 20 at 6:18
I tried to answer without the topic of multiplicative inverses $mod N$.
– DanielWainfleet
Jul 20 at 6:24
add a comment |Â
(1) implies that the function $f$ is 1-to-1. Without this we could only say that $S$ has at most $n$ members, which would be of no use.
– DanielWainfleet
Jul 20 at 6:18
I tried to answer without the topic of multiplicative inverses $mod N$.
– DanielWainfleet
Jul 20 at 6:24
(1) implies that the function $f$ is 1-to-1. Without this we could only say that $S$ has at most $n$ members, which would be of no use.
– DanielWainfleet
Jul 20 at 6:18
(1) implies that the function $f$ is 1-to-1. Without this we could only say that $S$ has at most $n$ members, which would be of no use.
– DanielWainfleet
Jul 20 at 6:18
I tried to answer without the topic of multiplicative inverses $mod N$.
– DanielWainfleet
Jul 20 at 6:24
I tried to answer without the topic of multiplicative inverses $mod N$.
– DanielWainfleet
Jul 20 at 6:24
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2856606%2fhow-to-prove-that-the-order-of-x-modulo-n-satisfies-r-leq-n%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
You need the condition that a and n be coprime, otherwise the question is formally nonsense. Keep in mind that powers of an element in a group form a periodic sequence, and the period is the order of the elements. Furthermore, inside a period, any two powers are different. As there are less then N different powers of the element a (since 0 is not a power), we are done.
– A. Pongrácz
Jul 19 at 13:20
Do You mean $x$ and $N$ are coprime?
– Aleksandr Berezutskii
Jul 19 at 13:25
Yes, indeed. Sorry.
– A. Pongrácz
Jul 19 at 13:26
Thank You! Your comment helped me to understand the fact that order modulo $N$ basically gives the number of different residues modulo $N$ that exist for different powers of $x$
– Aleksandr Berezutskii
Jul 19 at 13:59