Let $k, n$ be odd positve integers greater than $1$. Prove that if there a exists natural number $a$ such that $k|2^a+1, \ n|2^a-1$, then there is no natural number $b$ satisfying $k|2^b-1, \ n|2^b+1$.
Problem
Source: Polish Mathematical Olympiad 2016 P4- Final Round
Tags: number theory, Divisibility, order of an element, auyesl
08.04.2016 23:32
16.06.2018 21:45
A little bit different
14.01.2019 18:16
Here is another solution. I claim that, there is no pair $(a,b)$ of positive integers, such that, $(2^a-1,2^b+1)>1$ and $(2^a+1,2^b-1)>1$ hold simultaneously. Assume the converse, and for any pair, call it good if it obeys the condition. Take a good pair $(a,b)$ with the smallest possible sum. Clearly, $a\neq b$, so take wlog $a>b$. Let $a=kb+r$, and also see that, $b\nmid a$, thus $0<r<b$. Now, if $p\mid 2^a+1$ and $p\mid 2^b-1$, we get $p\mid 2^r+1$. Also, if $q\mid 2^b+1$ then $q\mid 2^a-1$ yields $q\mid (-1)^k 2^r -1$. If $k$ is even, we see that $q\mid 2^r-1$. Hence, $(b,r)$ is also good, contradicting with minimality of $(a,b)$. Similarly, if $k$ is odd, then $q\mid 2^r+1$, hence, $q\mid 2^b-2^r = 2^r(2^{b-r}-1)$. Also, $p\mid 2^b-1$ and $p\mid 2^r+1$ gives $p\mid 2^r(2^{b-r}+1)$. Hence, $p\mid 2^{b-r}+1$. Hence, $(b,b-r)$ is also good, again, contradiction with the minimality of $(a,b)$.
22.06.2021 17:25
01.04.2024 17:04
Lemma 1: Let $a,m$ be relatively prime numbers and $m \geq 2$. Let $\textrm{ord}_m(a)=r \in \mathbb{N}$ be the smallest $a^r \equiv 1 (\textrm{mod} \ m)$. Then $a^t \equiv 1 (\textrm{mod} \ m)$ if and only if $r|t$. Proof: Due to minimality of $t$ we have that $r \leq t$. Let $t=rq+u$ where $q \in \mathbb{Z}_{\geq 0}$ and $u \in \left \lbrace 0,...,r-1 \right \rbrace$. Assume that $r>0$. Then we get that: $$1 \equiv a^{t} \equiv a^{rq+u} \equiv a^u (\textrm{mod} \ m)$$which contradicts the minimality of r. Lemma 2: Let $a,m$ be relatively prime numbers and $m \geq 3$. Let $\textrm{hrd}_m(a)=s \in \mathbb{N}$ be the smallest natural number that $a^s \equiv -1 (\textrm{mod} \ m)$. Then $\textrm{ord}_m(a)=2s$ and $a^t \equiv -1 (\textrm{mod} \ m)$ if and only if $t=(2k+1)\cdot s$, where $k \in \mathbb{Z}_{\geq 0}$. Proof: Let $r=\textrm{ord}_m(a)$. Assume that $r \leq s$. Then $s=r+k$ for some $k \geq 0$. Then we get that: $$-1 \equiv a^s \equiv a^{r+k} \equiv a^k (\textrm{mod} \ m)$$It implies that $k \geq s$ ($k$ can't be $0$), because $m \geq 2$ and so $r \leq 0$ - contradiction. It means that $r>s$. Now assume that $r<2s$. Then we get that $2s=r+k$, $k>0$ and so: $$1 \equiv a^{2s} \equiv a^{r+k} \equiv a^k (\textrm{mod} \ m)$$and so $k \geq r$ and so $2s \geq 2r$, which contradicts the proven claim that $s<r$. Now let $a^t \equiv -1 (\textrm{mod} \ m)$ and $t=q\cdot s + u$, $q$ is a non-negative integer and $u \in \left \lbrace 0,...,s-1 \right \rbrace$. Assume that $u>0$. Then $$-1 \equiv a^{t} \equiv a^{sq+u} \equiv \pm a^u (\textrm{mod} \ m)$$from where we get that $a^u \equiv \pm 1 (\textrm{mod} \ m)$ which contradicts the minimality of $r$ in case of $1$ and $s$ in case of $-1$. It means that $s|t$. But if $t=2ks$, then definitely $a^t \equiv 1 (\textrm{mod} \ m)$. So we get $t=(2k+1)s$. Solution: Assume that $k|2^a+1$, $n|2^a-1$, $k|2^b-1$, $n|2^b+1$ hold simultaneously. Call $s=\textrm{hrd}_k (2)$, $t=\textrm{hrd}_k(2)$. Then we get that $$a=(2x+1)s, \quad b=(2y+1)t, \quad a=2zt, \quad b=2ws$$for some integers $x,y,z,w$. It yields $4zw=(2x+1)(2y+1)$ and so $2|(2x+1)(2y+1)$ which is an obvious contradiction.