Order

For discussing Olympiad Level Number Theory problems
sourav das
Posts:461
Joined:Wed Dec 15, 2010 10:05 am
Location:Dhaka
Contact:
Order

Unread post by sourav das » Tue Feb 14, 2012 10:36 am

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$" )

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: Order

Unread post by Masum » Tue Feb 14, 2012 11:18 am

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$.
One one thing is neutral in the universe, that is $0$.

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Order

Unread post by Phlembac Adib Hasan » Tue Feb 14, 2012 11:33 am

Masum Vaia wrote:If $k < m$ we are done. ... ... Now $\varphi(m)< m<k$ for $m>2$.
Will the first one be $k>m ?$
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Order

Unread post by *Mahi* » Tue Feb 14, 2012 2:58 pm

Masum wrote:
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$.
My solution too :) but there are a lot of places where mistakes might be made(I could have done some mistakes).

@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

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: Order

Unread post by Masum » Wed Feb 15, 2012 11:29 am

Phlembac Adib Hasan wrote:
Masum Vaia wrote:If $k < m$ we are done. ... ... Now $\varphi(m)< m<k$ for $m>2$.
Will the first one be $k>m ?$
Well then you may safely assume $k=r$. And you are done. Right? In the latter case, I have proven what we needed. :)
And hope Sourav is clear about the theorem by the time.
One one thing is neutral in the universe, that is $0$.

Post Reply