Order
-
- Posts:461
- Joined:Wed Dec 15, 2010 10:05 am
- Location:Dhaka
- Contact:
Let $(a,m)=1$ and there exists $k$ such that $a^{k}\equiv -1(mod$ $m)$ . Prove or disprove that there exists $r<m$ such that $a^r\equiv -1 (mod$ $m)$.
You spin my head right round right round,
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
Re: Order
If $k < m$ we are done. Otherwise from Euler's theorem, \[a^{\varphi(m)}\equiv1\pmod m\]
Now $\varphi(m)< m<k$ for $m>2$. And the theorem is trivial for $m=2$. So let $k=q\cdot\varphi(m)+r$ where $0<r<\varphi(m)<m$. Note that $r=0$ means $\varphi(m)|k$, forcing $m=1,2$. Therefore, \[a^k= (a^{\varphi(m)})^q\cdot a^r\equiv-1\pmod m\]
This gives \[a^r\equiv-1\pmod m\]
So from my solution you can conclude a better range for $r$.
Now $\varphi(m)< m<k$ for $m>2$. And the theorem is trivial for $m=2$. So let $k=q\cdot\varphi(m)+r$ where $0<r<\varphi(m)<m$. Note that $r=0$ means $\varphi(m)|k$, forcing $m=1,2$. Therefore, \[a^k= (a^{\varphi(m)})^q\cdot a^r\equiv-1\pmod m\]
This gives \[a^r\equiv-1\pmod m\]
So from my solution you can conclude a better range for $r$.
One one thing is neutral in the universe, that is $0$.
- Phlembac Adib Hasan
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
Re: Order
Will the first one be $k>m ?$Masum Vaia wrote:If $k < m$ we are done. ... ... Now $\varphi(m)< m<k$ for $m>2$.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules
Re: Order
My solution too but there are a lot of places where mistakes might be made(I could have done some mistakes).Masum wrote:
@Adib: Yes, the part after the first line assumes $k>m$.
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Re: Order
Well then you may safely assume $k=r$. And you are done. Right? In the latter case, I have proven what we needed.Phlembac Adib Hasan wrote:Will the first one be $k>m ?$Masum Vaia wrote:If $k < m$ we are done. ... ... Now $\varphi(m)< m<k$ for $m>2$.
And hope Sourav is clear about the theorem by the time.
One one thing is neutral in the universe, that is $0$.