Number theory and modular arithmetic

61 Views Asked by At

This is a number theory problem posed.

Let $k\in\mathbb{N}$ such that $3\nmid k-2$. Show that there is an $m\in\mathbb{N}$, such that $x$ is an odd number, where

$$ x = \left\{ \begin{array}{ll} \dfrac{(2k-1)2^{2m}-1}{9} & \quad 3 \ | \ k-1\\ \dfrac{(2k-1)2^{2m-1}-1}{9} & \quad 3 \ | \ k \end{array} \right. $$

4

There are 4 best solutions below

0
On BEST ANSWER

I'm not sure if I'm understanding your question correctly, so correct me if I'm wrong.

We have 6 cases total: For $3 \mid k - 1$, we have $k \equiv 1 \pmod{9}$, $k \equiv 4 \pmod{9}$ and $k \equiv 7 \pmod{9}$. For $3 \mid k$, we have $k \equiv 0 \pmod{9}$, $k \equiv 3 \pmod{9}$ and $k \equiv 6 \pmod{9}$.

(Case 1) If $k \equiv 1 \pmod{9}$, then we choose $m = 3$, and we have: $$ (2k - 1)2^{2m} - 1 = 128k - 65 \equiv 63 \equiv 0 \pmod{9} $$ (Case 2) If $k \equiv 4 \pmod{9}$, then we choose $m = 1$, and we have: $$ (2k - 1)2^{2m} - 1 = 8k - 5 \equiv 27 \equiv 0 \pmod{9} $$ (Case 3) If $k \equiv 7 \pmod{9}$, then we choose $m = 2$, and we have: $$ (2k - 1)2^{2m} - 1 = 32k - 17 \equiv 207 \equiv 0 \pmod{9} $$ (Case 4) If $k \equiv 0 \pmod{9}$, then we choose $m = 2$, and we have: $$ (2k - 1)2^{2m-1} - 1 = 16k - 9 \equiv -9 \equiv 0 \pmod{9} $$ (Case 5) If $k \equiv 3 \pmod{9}$, then we choose $m = 1$, and we have: $$ (2k - 1)2^{2m-1} - 1 = 4k - 3 \equiv 9 \equiv 0 \pmod{9} $$ (Case 6) If $k \equiv 6 \pmod{9}$, then we choose $m = 3$, and we have: $$ (2k - 1)2^{2m-1} - 1 = 64k - 33 \equiv 351 \equiv 0 \pmod{9} $$

0
On

Let's take the case $3\,|\,k-1$. Write $k=3n+1$.

We want to find $m\in \mathbb N$ such that $2^m\times (6n+1)-1$ is odd and divisible by $9$. It is odd regardless of what $m$ is (even if $m=0$), so we can ignore that condition. Thus we just want it to be divisible by $9$. We compute $$0\equiv 2^m\times 6n+2^m-1\pmod 9\implies 1-2^m\equiv 2^m\times 6n \pmod 9$$

Case by case we see that $$n\equiv \{0,1,2,3,4,5,6,7,8\}\implies m=\{1,2,4,6,2,4,6,2,4\}$$

where we have just chosen particular values of $m$ that work.

The case $3\,|\,k$ should be similar.

0
On

$$2^{2m}=(1+3)^m\equiv1+3m\pmod9$$

$$f(m,k)=(2k-1)2^{2m}\equiv(2k-1)(1+3m)$$

If $k-1=3n,$

$$f(m,3n+1)\equiv(6n+1)(3m+1)\equiv1+3(m+2n)\pmod9$$

We need $m+2n\equiv0\pmod3\iff m\equiv-2n\equiv n\pmod3$

Similarly for the second case

0
On

If $3 \nmid (k-2) \implies 3 \nmid (2k-4) \implies 3 \nmid (2k-1)$. This is to ensure that $x$ is an integer. Clearly $x$ will be odd as the numerator in both cases is odd. Now, we need to ensure that $9$ divides the numerator.

If the power of $2$ is even, as in the first case, it is $1 \pmod{3}$. We can check that it takes all values $1,4,7 \pmod{9}$. Else, if the power is odd, as in the second case, it is $2 \pmod{3}$. It takes values $2,5,8 \pmod{9}$.

If $3 \mid (k-1)$, then $2k-1 \equiv 1 \pmod{3}$ which can take the values $1,4,7 \pmod{9}$. $2^{2m}$ can respectively take the values $1,7,4 \pmod{9}$. This makes $(2k-1)2^{2m} \equiv 1 \pmod{9}$. This makes the numerator divisible by $9$. You can similarly work out the other case.