Latex and better formulation. Prove that there exists a positive integer $n$, such that the remainder of $3^n$ when divided by $2^n$ is greater than $10^{2021} $.

VicKmath7 wrote: Latex and better formulation. Prove that there exists a positive integer $n$, such that the remainder of $3^n$ when divided by $2^n$ is greater than $10^{2021} $. Thanks edited

Take n=2^t for some large nonnegative integer t It is easy to prove that v_{2}(3^n-1)=t+2 Now take non-negative integer x such that it is a remainder of 3^n by modulo 2^n. Obviously x is neither 0 or 1, then x>1. Since both 3^n-1 and 3^n-x are divisible by 2^{t+2}, we have x-1 divisible by 2^{t+2} but greater than 0. Therefore, x is bigger than 2^{t+2}, which solves the problem. Sorry, it is my new account so aops doesn't allow new users to use LaTeX.

We prove the remainder cannot be bounded (as a function of $n$). Denote $$3^n =a_n 2^n+ b_n$$where $a_n,b_n\in \mathbb{N}, 0\le b_n<2^n$. Seeking for contradiction, suppose there exists $A>0$ such that $b_n<A, \forall n\in\mathbb{N}$. Further $$\left( \frac{3}{2}\right)^n=a_n+\frac{b_n}{2^n}$$Let now $N$ is large enough, such that $\frac{3A}{2^n}<\frac{1}{2}, \forall n>N$ We have $$\left( \frac{3}{2}\right)^{n+1}=\frac{3}{2}a_n+\frac{3b_n}{2^{n+1}}$$Assuming $\frac{3}{2}a_n$ is not integer brings us to contradiction since $\frac{1}{2}+\frac{3b_n}{2^{n+1}}$ is less than $1$ but is large enough to be represented as $\frac{b_{n+1}}{2^{n+1}}$ for some $0\le b_{n+1}<A$. Thus, $a_{n+1}=\frac{3}{2}a_n,\forall n>N$ which is not possible to hold since $a_n\in \mathbb{N},\forall n.$

Let $k=10^{2021} $. Consider numbers $3^{n}$, $3^{n+1}$, ... , $3^{n+k}$. If for some x the remainder of $3^{n+x}$ when divided by $2^{n}$ is greater than k, the remainder when divided by $2^{n+x}$ would also be greater than k. We consider k+1 numbers so $3^x \equiv 3^y \mod 2^n$ for some x and y ($n \le y<x \le n+k $ and $ x-y \le k$). $3^{x-y} \equiv 1 \mod 2^n$ $3^{x-y}-1 \ge 2^n$ $3^{k}-1 \ge 2^n $, which is wrong for great n.

RegulusB-8 wrote: Take $n=2^t$ for some large nonnegative integer $t$ It is easy to prove that $v_{2}(3^n-1)=t+2$ Now take non-negative integer $x$ such that it is a remainder of $3^n$ by modulo $2^n$. Obviously $x$ is neither 0 or 1, then $x>1$. Since both $3^n-1$ and $3^n-x$ are divisible by $2^{t+2}$, we have $x-1$ divisible by $2^{t+2}$ but greater than 0. Therefore, $x$ is bigger than $2^{t+2}$, which solves the problem. Sorry, it is my new account so aops doesn't allow new users to use LaTeX. Here.

This felt a bit direct, even for a P1 Let $k$ denote the largest possible value of $3^m \mod 2^m$, for $m > 2^{100}$, assuming that $3^m \mod 2^m$ is bounded by $10^{2021}$ Observe that $3^{m+1} \mod 2^{m+1}$ is either $3k$ or $3k + 2^m$. This is true because both of these values are less than $2^m + 3 \times 10^{2021} < 2^{m+1}$. This contradicts the maximality of $k$, since $3k, 3k + 2^m > k$

Quick Sketch: Pick $S,T$ so that $3^S>10^{2021}$ and $2^T>3^S$. Then, setting $n = 2^T+S$, by LTE we get that \[ 2^{T+2} \mid 3^n-3^S \]Furthermore, if $a \equiv b \pmod n$, then $a \equiv b' \pmod{kn}$ implies $b' \geq b$ (given that $0 \leq b < n$.) Applying this simple fact shows that \[ 3^n \equiv r \pmod{2^n} \]implies $r \geq 3^s > 10^{2021}$. $\blacksquare$ $\blacksquare$ $\blacksquare$

Edit: The USA problem mentioned was JMO 2016/2.

Lemma 1. If $3^n$=a (mod $2^k$) where n>=k, and if $3^n$=b (mod $2^n$), then b>=a. If we take such k that $2^k$>3*$10^{2021}$ then it is obvious that if $3^k$=i (mod $2^k$) we can raise the power of 3 and eventually we will get such power k+j (j>=0) that $3^{k+j}$ = L (mod $2^k$) where $10^{2021}$ < L < 3*$10^{2021}$ < $2^k$. If $3^{k+j}$=N (mod $2^{k+j}$) and since $2^{k+j}$>=$2^k$, by Lemma 1 we get that N>L>$10^{2021}$.

Inshaallahgoldmedal wrote: Prove that there exists a positive integer $n$, such that the remainder of $3^n$ when divided by $2^n$ is greater than $10^{2021} $. Consider the following sequence $\{a_i\}_{i\ge 1}$ such that $3^i\equiv a_i\pmod{2^i}$ and $0\le a_i<2^i$. Then we have $a_{n+1}\equiv 3a_n\pmod {2^n}$. Now for the sake of contradiction assume that $\{a_i\}_{i\ge 1}$ is bounded; say $M=\max\{a_i: i\ge 1\}=a_T$ for all $i\ge 1$. Now choose $n$ such that $2^n> 3M$. Then we have $a_{T+1}\equiv 3a_T=3M\pmod {2^n}$, but due to the choice of $n$ we must have $a_{T+1}=3M$, a contradiction to the maximality of $M$.

Let $3^n = a_n2^n + b_n$ where $0 < b_n < 2^n$. Then, we have $2^n(2a_{n+1} - 3a_n) = 3b_n - b_{n+1}$ for all $n \in \mathbb{Z^+}$. Now fix some $n \in \mathbb{Z^+}$. If $2a_{n+1} = 3a_n$, then $b_{n+1} = 3b_n$. If $2a_{n+1} > 3a_n$, then $b_n > \frac{2^n}{3}$ and finally if $2a_{n+1} < 3a_n$, then $b_{n+1} > 2^n$. Now choose $m$ such that $2^m > 10^{10000}$. Now if for some $k \geq m$, if $2a_{k+1} > 3a_k$ or $2a_{k+1} < 3a_k$, then clearly one of $b_k$ or $b_{k+1}$ will be bigger than $\frac{2^k}{3} \geq \frac{10^{10000}}{3} > 10^{2021}$, and we will be done. So assume $2a_{k+1} = 3a_k$ for all $k \geq m$. So this means $b_{k+1} = 3b_k$ for all $k \geq m$. But since $b_i \geq 1$ for all $i$, this means that the sequence $\{b_k\}_{k\geq m}^{\infty}$ is unbounded, and we are also done in this case.

Inshaallahgoldmedal wrote: Prove that there exists a positive integer $n$, such that the remainder of $3^n$ when divided by $2^n$ is greater than $10^{2021} $. Define $R(a,b)$ to be the Remainder when $a$ is divided by $b$ FTSOC Assume that there doesn't exist any such $n$. Then $10^{2021}>R(3^n,2^n)$ for all natural number $n$. Let $S=\{n| 2^n>10^{10^{2021}}\}$ then Now as $R(3^n,2^n)$ is bounded So there must be $n_1\in S$ such that $R(3^{n_1},2^{n_1})$ is maximum among all $n\in S$. But then as $R(3^{n_1+1},2^{n_1+1})>3R(3^{n_1},2^{n_1})$ This is only possible if $2^{n_1+1}<3R(3^{n_1},2^{n_1})<3\times 10^{2021}$ But as $n_1+1\in S$ So it is Contradiction, We are done!

My solution seems different from others. Assume there isn't such number. Let $n$ be number such that $n>max\{v_2(3-1),v_2(3^2-1),\cdots,v_2(3^{10^{2021}}-1)\}$. Let $b_i$ be remainder when $3^i$ divided by $2^i$. Then look at $b_{n},b_{n+1},\cdots,b_{n+10^{2021}}$. Since $1\leq b_i\leq 10^{2021}$ we have $b_{n+i}=b_{n+j}$ for some $0\leq\ i<j\leq 10^{2021}$ $\implies$ $2^{n+i}\mid 3^{n+j}-3^{n+i}$ $\implies$ $2^n\mid 3^{j-i}-1$. We know that $1\leq j-i\leq 10^{2021}$. But since $n>max\{v_2(3-1),v_2(3^2-1),\cdots,v_2(3^{10^{2021}}-1)\}$, we get contradiction. So there is such $n$. And we are done!

A more detailed version of #16, posting for the archive. Let $S, T$ be such that $2^T>3^S>10^{2021}$. We prove there exists $n>S$ such that $3^n\equiv 3^S \pmod{2^T}\Leftrightarrow 3^{n-S}\equiv 1 \pmod{2^T}$. By LTE we would need $$v_2(3^{n-S})=v_2(3-1)+v_2(3+1)+v_2(n-S)-1=v_2(n-S)+2\geq T.$$And such $n$ clearly exists, for example pick $n_0=2^T+S$, which works since it's greater than $S$. Now note that from the system of modular congruences $$\begin{cases} 3^{n_0} \equiv r \pmod{2^{n_0}}\\ 3^{n_0} \equiv 3^S \pmod{2^T}\end{cases}$$it follows that $r\geq 3^S>10^{2021}$, because $r<2^{n_0}$ and $2^{n_0}>2^T$ ($n_0=2^T+S>2^T>T$). Done.

I see very "complex" solutions (with respect to my solution), I have a solution through very basic mathematics

hectorleo123 wrote: I see very "complex" solutions (with respect to my solution), I have a solution through very basic mathematics You are welcome to show it to us.

Have $\left( \frac{3}{2}\right)^n=(1,5)^n$ Be $p_n=$ fractional part of $(1,5)^n$ $\rightarrow p_n 2^n \equiv3^n(mod 2^n) ...(\alpha)$ We know that $p_n<1$ If the integer part of $(1,5)^n$ is even: we will call "reset" when $\frac{3}{2}p_n>1$ given that $p_{n+1}=\frac{3}{2}p_n-1$ Let us note that the "reset" occur when $p_n>2/3$ If the integer part of $(1,5)^n$ is odd: we will call "reset" when $\frac{3}{2}p_n+\frac{1}{2}>1$ given that $p_{n+1}=\frac{3}{2}p_n-\frac{1}{2}$ Let us note that the "reset"occur when $p_n>1/3$ In both cases $p_n>1/3$ We will prove that there are infinite "reset": Suppose we have a k that does not have "reset" If the integer part of $(1,5)^k$ is odd: $p_{k+1}=\frac{3}{2}p_k$ $p_k \le 1/3$ $\rightarrow p_{k+1}<1/2$ how do you multiply by 1,5 (from $p_t$ to $p_{t+1}$) then it exists $u>k$ such that $1/2>p_u>1/3$and we have not done any "reset" but now there will be a "reset". If the integer part of $(1,5)^k$ is even: $p_{k+1}=\frac{3}{2}p_k+\frac{1}{2}$ $p_k \le 2/3$ $\rightarrow p_{k+1}<1,5$ but there is no "reset" then $p_k<1$ how do you multiply by 2 (from $p_t$ to $p_{t+1}$) then it exists $u>k$ such that $1>p_u>2/3$ and we have not done any "reset" but now there will be a "reset". Now we can choose $g$ large enough such that $ p_g $ has "reset" If $ p_g $ has "reset" $\rightarrow p_b>\frac{1}{3}$ By ($\alpha$): $p_g 2^g\equiv3^g(mod 2^g)$ $\rightarrow$ what we want is $>\frac{2^g}{3}$ We can make $g$ large such that it is $>10^{2021}$ $_\blacksquare$

Assume contrary. Let the set of remainders provided when $3^n$ divided by $2^n$ be a finite set. Some of the numbers are remainders for finite times and some of them are infinite. Take $n\geq M$ such that all the remainders provided when $3^n$ divided by $2^n$ takes place for infinite times. Let $T$ be the maximum remainder among these remainders. $3^m\equiv T(mod 2^m)$ and $3^k\equiv T (mod 2^k)$ so we have $2^m|3^m-T$ and $2^k|3^k-T$ which gives us that $2^{m+k}|3^{m+k}-(3^m+3^k)T+T^2$ $3^{m+k}\equiv (3^m+3^k)T-T^2(mod 2^{m+k})$ and $(3^m+3^k)T-T^2\equiv T(3^m-T)+3^kT\equiv 3^kT(mod 2^m)$ Take $m$ sufficiently large. Then, $3^kT<2^m<2^{m+k}$ which gives us that $3^{m+k}\equiv 3^kT(mod 2^m)$ such that $3^kT$ is the remainder because $3^kT<2^m$. The remainder provided when $3^{m+k}$ is divided by $2^{m+k}$ is larger or equal to the remainder provided when $3^{m+k}$ is divided by $2^m$. It results in a contradiction because $3^kT>T$ but $T$ is the biggest remainder $\geq M$.

Easier version of RMM 2024/4 , here @dgrozev's solution shows that we can replace the constant in the problem by any $o(2^n)$ function. The argument simplifies a bit for the constant case (done here). Let $n$ be large and suppose all remainders are bounded by a constant. If $3^n=q_n \cdot 2^n + r_n$ (with $r_n \neq 0$ for all $n$ since $2^n$ does not divide $3^n$), then $q_{n+1} \cdot 2^{n+1} + r_{n+1} = 3^{n+1}= 3q_n \cdot 2^n + 3r_n$. Then, $r_{n+1}\equiv 3r_n \pmod{2^n}$. Since their diffrence is bounded by a constant, for large $n$ we must have $r_{n+1} = 3r_n$. But then for some fixed $N$ among these large ones we have $r_{N+k} = 3^kr_N \geq 3^k$ which is unbounded, contradiction.

We shall use the existence of order. Say $r$ is the remainder. Take $3^x > 10^{2021}$, $2^y > 3^x$, so $r = 3^x$ here since $2^y$ is larger. We know there exists $\text{ord}_3(2^y)$, so for sufficiently large $m$, we have $3^{x + m\cdot\text{ord}_3(2^y)} \equiv 3^x\mod{2^y}$. So we may simply take $n$ as $x + m\cdot\text{ord}_3(2^y)$, which means $r = 3^x > 10^{2021}$.

Claim (RMM 2024/4): If $a,b$ are positive integers greater than $1$ satisfying $a \nmid b$, there exist infinitely many positive integers $n$ so that the nonnegative remainder when $b^n$ is divided by $a^n$ is at least $\frac{2^n}{n}$. Proof: Suppose for some $a,b$ with $a\nmid b$ that this was false. Let $r_n$ be the remainder when $b^n$ is divided by $a^n$. Note that for each $n$, $r_n$ is positive integer. If $a > b$, then $r_n = b^n$ exceeds $\frac{2^n}{n}$ for large enough $n$, a contradiction. Thus, $a < b$. Subclaim: $r_{n+1} = b \cdot r_n$ for all $n > N$. Proof: Suppose otherwise. Note that $b^n \equiv r_n \pmod{a^n}$, so if we let $b^n = k a^n + r_n$ for some positive integer $k$, multiplying both sides by $b$ gives that $b^{n+1} = kb a^n + b r_n$. This means that $r_{n+1}$ is $br_n$ modulo $a^n$. Let $r_{n+1} = x\cdot a^n + b r_n$ for some positive integer $x$. We then have $r_{n+1} > x a^n \ge a^n$. Since $n + 1 > N$, $a^n < \frac{2^{n+1}}{n+1}$ must hold. However, since $n > 1$, $\frac{2^{n+1}}{n+1} < \frac{2^{n+1}}{2} = 2^n \le a^n$, a contradiction. Therefore, $r_{n+1} = b \cdot r_n$. $\blacksquare$ Now fix some $m > N$. We can inductively get $r_{m+k} = b^k r_m$. This implies that\[ b^k r_m < \frac{2^{m + k}}{m + k} \implies \left( \frac b2 \right)^k < \frac{2^m }{(m + k) \cdot r_m} < \frac{2^m}{m \cdot r_m}\](which is true as $r_m > 0$). Since $1 < a < b$, $b > 2$, so choosing $k$ large enough gives a contradiction. $\square$ Now, fix $a = 2, b = 3$ and choose $N$ large enough so that $\frac{2^n}{n} > 10^{2021} \forall n \ge N$. Note that by our claim, we can find $n \ge N$ where the remainder when $3^n$ is divided by $2^n$ is at least $\frac{2^n}{n} > 10^{2021}$, which finishes.