x is rational implies y is rational

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pohoatza

1145 posts

pohoatza

#1 h Jun 28, 2007, 7:24 PM • 11 Y

Y by Davi-8191, Math-Ninja, Adventure10, megarnie, centslordm, erfanmohseni2022, OronSH, Mango247, and 3 other users

For $x \in (0, 1)$ let $y \in (0, 1)$ be the number whose $n$ -th digit after the decimal point is the $2^{n}$ -th digit after the decimal point of $x$ . Show that if $x$ is rational then so is $y$ .

Proposed by J.P. Grossman, Canada

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

edriv

232 posts

edriv

#2 h Jun 28, 2007, 8:35 PM • 9 Y

Y by Pluto1708, hakN, Adventure10, centslordm, Mathlover_1, Mango247, MS_asdfgzxcvb, and 2 other users

Let $f(n)$ , $n=1,2,\ldots$ be the decimal representation of x. Then the decimal representation of y is $g(n) = f(2^{n})$ .
x is rational, therefore the sequence is eventually periodic, that is, there are $t,x_{0}\in \mathbb{N}^{+}$ such that for all $x > x_{0}$ we have $f(x) = f(x+t)$ .
By induction, we get that for all $x,y>x_{0}$ such that $t \mid x-y$ we have $f(x) = f(y)$ .

Let's write $t = 2^{k}d$ , with k nonnegative and d odd.
For all $x>k$ , we have $t \mid 2^{x+\phi(d)}-2^{x}= 2^{x}(2^{\phi(d)}-1)$ because $2^{k}\mid 2^{x}$ and ${d \mid 2^{\phi(d)}-1}$ .
Therefore, for all $x>\mbox{max}(k,x_{0})$ we have $f(2^{x+\phi(d)}) = f(2^{x})$ , and finally $g(x+\phi(d)) = g(x)$ .
So, also $g(x)$ is eventually periodic.
And y is rational

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bulingchen

1 post

bulingchen

#3 h Sep 18, 2008, 2:03 PM • 3 Y

Y by centslordm, Adventure10, Mango247

g(n)=f(2^n)

let d be the period of x

then d*2^n is also a period of x

x:1,2,...,d;d+1,d+2,...,2d;......;d*2^n-(d-1),...,d*2^n;......
y: 1 2 ...... d ......

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathbuzz

803 posts

mathbuzz

#4 h Mar 14, 2014, 5:44 AM • 2 Y

Y by centslordm, Adventure10

$x$ is rational .Suppose , the decimal representation of $x$ contains infinitely many non-zero digits after decimal.
So , the digits in its decimal representation eventually will appear periodically.
let , the minimal period be $k$ (after the digits start appearing periodically)
hence , there exists some $M\in N$ such that , for $n_1 , n_2 \ge M$ ,
$2^{n_1}$ th and $2^{n_2}$ th digits after decimal are equal in the decimal representation of $x$ if
$2^{n_1}=2^{n_2}(mod k)$ .
Say , $k=2^p.q$ where $p\ge 0$ and $q$ is odd .
Now , note that , $2^{n_1}=2^{n_2} (mod k)$ if and only if $n_1=n_2(mod r)$
where $r$ = order of 2 moduldo $q$ .
So , there exists $M$ such that , for $n_1,n_2 \ge M$ , $n_1$ and $n_2$ th digit in the decimal representation of $y$ are equal if and only if $n_1=n_2(mod r)$ . hence , y is rational .

On the other hand , if $x$ contains only finitely many non-zero digits after the decimal place , then y also contains only finitely many non-zero digits after decimal , hence y is rational in this case too .

This post has been edited 1 time. Last edited by mathbuzz, Nov 25, 2015, 9:28 AM
Reason: small error fixed

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sketshup

6 posts

Sketshup

#5 h Feb 1, 2015, 1:00 PM • 3 Y

Y by centslordm, Adventure10, Mango247

if $x$ is rationnal, then either its decimal representation contains a finite number of digits, or it's digits sequence is eventually periodic, after a certain number of first digits.

Dealing with the first case is not difficult at all: since $x$ has an $m$ finite number of digits after the decimal point, then $y$ has at most $\log{m}$ digits after the dot point, hence $y$ is rationnal as well.

Let's move to the second case. Since $x$ has infinitly many digits after the decimal point, $y$ has also infinitly many digits. So it remains to prove that, if the digits of $x$ are eventually periodic, so are the digits of $y$ .

Note $K$ the period of the digits of $x$ . It's enough to prove that $(2^n)$ is eventually periodic modulo $K$ . If $K$ is a power of $2$ , say $K=2^a$ , then eventually the sequence will be congruent to $0$ mod $K$ . If $K$ is not a power of 2. Set $K = 2^a.m$ where m is an odd integer.

Suppose the assumption is true. That is $(2^n)$ is eventually periodic modulo $K$ . This is equivalent to the following: there exists an integer $j$ such that starting from an $n$ sufficiently large we get for all $N > n$ , $2^{N+j} = 2^N [K]$ , or $2^{N+j-a} = 2^{N-a} [q]$ , or $j = 0[ord_2(q)]$ . Thus, taking $j = ord_2(q)$ , the assumption remains true, and thus the sequence $(2^n)$ is eventually periodic modulo $K$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathPanda1

1135 posts

MathPanda1

#6 h Sep 25, 2015, 10:55 PM • 5 Y

Y by Chandrachur, BaronPit, centslordm, Adventure10, Mango247

Sketshup wrote:

Note $K$ the period of the digits of $x$ . It's enough to prove that $(2^n)$ is eventually periodic modulo $K$ . If $K$ is a power of $2$ , say $K=2^a$ , then eventually the sequence will be congruent to $0$ mod $K$ . If $K$ is not a power of 2. Set $K = 2^a.m$ where m is an odd integer.

It seems like everyone let $K = 2^a \cdot m$ , but the following solution will not (so is it right?):

Consider $2^1, 2^2, ..., 2^{K+1} \pmod K$ . There are $K+1$ numbers in this sequence, so by Pigeonhole Principle, there exists $a$ and $b$ ( $a<b$ ) such that $2^a \equiv 2^b \pmod K$ . Thus, $2^{a+i} \equiv 2^{b+i} \pmod K$ for all nonnegative integers $i$ i.e. $2^{n} \equiv 2^{n+b-a} \pmod K$ for all sufficiently large $n$ i.e. $(2^n)$ is eventually periodic modulo $K$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

droid347

2679 posts

droid347

#7 h Nov 13, 2015, 12:57 AM • 3 Y

Y by centslordm, Adventure10, Mango247

We begin with a lemma.

LEMMA. If $t\in (0,1)$ is rational, then the decimal representation of $t$ repeats after some time, and vice versa.

Proof. The backwards direction is well known. For the forwards direction, assume there are $j$ non-repeating digits before the “block” of repeating digits. We can simply take $\frac{l}{10^j}+\frac{m}{10^j}$ for appropriate the appropriate $l$ , which is clearly rational, and for $m\in (0,1)$ , a repeating decimal that begins repeating immediately. Thus, we only need to prove for repeating decimals that begin to repeat immediately.

We denote the number of digits after which the decimal representation of $m$ repeats to be $r$ . However, note that we have $r=p\cdot w$ , where $p$ is a positive integer in $[1, 10^{r}-1]$ and $w=\overline{0.00\ldots 0100\ldots 0100\ldots 0100\ldots}$ where there are $r-1$ zeroes between each pair of ones. We can show that $w$ is rational by summing the geometric sequence $\frac{1}{10^r}+\frac{1}{10^{2r}}+\frac{1}{10^{3r}}\ldots=\dfrac{\frac{1}{10^r}}{1-\frac{1}{10^r}}$ with a well-known formula, which is rational. $\square$

Now, for the problem, note that by the lemma we only need to prove that $y$ repeats; but this is equivalent to proving that $2^n \pmod{r}$ cycles as $n$ increases over positive integers for positive integer $r$ . However, by Euler’s totient theorem, we have $2^{\phi(r)}\equiv 1\pmod{r}$ , so we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

LMat

42 posts

LMat

#8 h Sep 29, 2017, 1:44 PM • 3 Y

Y by centslordm, Adventure10, Mango247

Is this question basically asking if $2^n$ is eventually periodic modulo any number? I thought that would just go without saying since there is a finite number of remainders and multiplying a number with a particular remainder by $2$ always produces the same new remainder?

This post has been edited 1 time. Last edited by LMat, Sep 29, 2017, 1:44 PM
Reason: Inlining latex

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Wizard_32

1566 posts

Wizard_32

#9 h Apr 19, 2018, 5:56 PM • 2 Y

Y by centslordm, Adventure10

LMat wrote:

Is this question basically asking if $2^n$ is eventually periodic modulo any number? I thought that would just go without saying since there is a finite number of remainders and multiplying a number with a particular remainder by $2$ always produces the same new remainder?

Yep, that's why this problem is nearly trivial.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Wizard_32

1566 posts

Wizard_32

#10 h Apr 19, 2018, 6:02 PM • 6 Y

Y by third_one_is_jerk, centslordm, Pratik12, wasikgcrushedbi, Adventure10, Flint_Steel

My solution:
Let $x=0.x_1x_2x_3 \cdots$ Since $x$ is rational, hence we can write $x=0.\overline{x_1x_2 \cdots x_m}$ . Then $y=0.x_2x_4x_8x_{16} \cdots$
Now, it is easy to see that if $i \equiv j \pmod{m}$ , then $x_{i}=x_j$ . Thus it suffices to show that the sequence $\langle 2^{n} \rangle_{n=1}^{\infty}$ is periodic modulo any number $m$ . This is clear by the pigeonhole principle, since we must have $2^k \equiv 2^l \pmod{m}$ for some $k \ne l$ , and this clearly implies that the sequence is periodic. $\blacksquare$

This post has been edited 2 times. Last edited by Wizard_32, Apr 19, 2018, 6:03 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#12 h Feb 5, 2019, 7:12 AM • 5 Y

Y by centslordm, Adventure10, Mango247, Mango247, Mango247

Lemma: The sequence of digits of the decimal expansion of a number is periodic iff the number is rational.

Proof of Lemma: The only if direction is very easy, since if the decimal expansion is periodic, we can write the number as an infinite geometric series, which we know sums to a rational number. Now let us prove the if direction. Consider long dividing $m/n$ . We will get a sequence of remainders:
$\begin{align*} 10m&=q_1n+r_1 \\ 10r_1&=q_2n+r_2 \\ 10r_2&=q_3n+r_3 \\ &\vdots \end{align*}$ The sequence $q_1,q_2,\ldots$ are the digits of $m/n$ . Since $0 \le r_i \le n-1$ , by pigeonhole, there must exist $r_i=r_j$ , and hence $q_i=q_j$ , for some $0\le i,j\le n$ , $i\not = j$ . Then $q_{i+k}=q_{j+k}$ for all $k\ge 1$ . Hence, the sequence of digits is periodic. $\square$

Let $k$ be the period of the decimal expansion of $x$ . In order to show that $y$ is rational, we must show that its decimal expansion is periodic. This is equivalent to showing that $2^n$ is periodic $\pmod{k}$ . Since $2^{\phi(k)} \equiv 1 \pmod{k}$ , the sequence $2^n \pmod{k}$ must be periodic.

This post has been edited 2 times. Last edited by pad, Feb 5, 2019, 6:48 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AlastorMoody

2125 posts

AlastorMoody

#13 h Oct 1, 2019, 7:48 PM • 7 Y

Y by Pluto1708, mueller.25, Purple_Planet, cadaeibf, centslordm, Adventure10, Mango247

Solution

This post has been edited 1 time. Last edited by AlastorMoody, Oct 1, 2019, 7:49 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HKIS200543

380 posts

HKIS200543

#14 h Aug 6, 2020, 3:36 PM • 3 Y

Y by animath_314159, centslordm, Mango247

Let $x_k$ and $y_k$ denote the $k$ -th digits of $x$ and $y$ respectively. Obviously $y_k = x_{2^k}$ . It is well known that a number rational if and only if its decimal representation is eventually periodic.

We shall invoke this fact repeatedly. Let $T_1$ be the period of the decimal representation of $x$ and write $T_1 = 2^n m$ for an odd integer $m$ . Let $T = \varphi(m)$ . I claim that the decimal representation of $y$ repeats with period $\varphi(m)$ . Observe that
$a \equiv b \mod{T} \implies 2^a \equiv 2^b \pmod{m} .$ If $a$ and $b$ are larger than $n$ we can conclude the stronger $2^a \equiv 2^b \pmod{T_1}$ since they are both divisible by $2^n.$ . Thus if $a \equiv b \pmod{m}$ for big enough $a,b$ , then $x_{2^a} = y_{2^b}$ . Immediately $y_a = y_b$ . Hence the decimal representation is periodic. Hence $y \in \mathbb{Q}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

brainiacmaniac31

2170 posts

brainiacmaniac31

#15 h Mar 3, 2021, 7:02 AM • 1 Y

Y by centslordm

Storage

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

isaacmeng

113 posts

isaacmeng

#16 h Apr 10, 2021, 12:59 PM • 1 Y

Y by centslordm

It is trivial that $x\in\mathbb{Q}\iff x\text{ has terminating or eventually periodic digits}$ . When $x$ has terminating digits, the problem is trivial, otherwise write $x=0.a_1\cdots a_kb_1\cdots b_lb_1\cdots b_lb_1\cdots b_l\cdots$ , where $b_1\cdots b_l$ is the repeating part. Notice an obvious fact, that the sequence $(f_n)_{n=1}^{\infty}$ defined by: $f_1$ arbitrary, and $\forall n\ge 1$ , $f_{n+1}$ is the residue then $2f_n$ is divided by $m$ , must be periodic. Then $y=0. a_2 a_4 \cdots a_{2^{[log_2 k]}}b_{2^{[log_2k]+1}-k} \cdots.$ By the above claim, set $f_1=2^{[log_2k]+1}-k$ we can see that $y$ must be eventually periodic.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bora_olmez

277 posts

bora_olmez

#17 h Jul 24, 2021, 5:35 PM • 1 Y

Y by centslordm

Notice that as $x$ is rational its decimal is eventually periodic with say period $p \in \mathbb{N}$ and notice that $2^k$ is also periodic $\pmod{p}$ meaning that the decimal representation of $y$ is also eventually periodic and $y \in \mathbb{Q}$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

hakN

429 posts

hakN

#18 h Aug 1, 2021, 1:45 PM • 1 Y

Y by centslordm

It is well known that a number is rational iff its decimal representation is periodic.
So since $x$ is rational, let $m$ be the length of the period of $x$ .
But, since $2^k \pmod{m}$ is periodic, the decimal representation of $y$ is periodic, implying that $y$ is rational.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SPHS1234

466 posts

SPHS1234

#19 h Oct 15, 2021, 4:58 PM

Y by

Let $x$ have period length $n=2^a.b$ where $b$ is odd.Then $y$ will be periodic from the $a^{th}$ digit after the decimal point with a period $\phi (b)$ because
$2^{a+\phi(b)} \equiv 2^a \pmod{2^a.b}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

oVlad

1721 posts

oVlad

#20 h Oct 25, 2021, 12:22 PM • 1 Y

Y by pavel kozlov

Assume $x$ has some random digits after the decimal point and then periodic of period $k.$

Then, $y$ will also have some random digits and then, it will be periodic of period $\varphi(k)$ because $i\equiv j\bmod{\varphi(k)}\iff 2^i\equiv 2^j\bmod{k}$ for big enough $i$ and $j,$ that is, $i$ and $j$ greater than $\nu_2(k).$

This post has been edited 1 time. Last edited by oVlad, Oct 25, 2021, 12:22 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

554183

484 posts

554183

#21 h Nov 5, 2021, 2:08 PM

Y by

Let $x$ have period $\ell$ . Note that $2^y$ eventually cycles modulo $\ell$ , since if $\ell$ is even, then we are trivially done. If $\ell$ is odd, we have $2^{\phi(\ell)} \equiv{1} \pmod{\ell}$ and therefore $2^{a+\phi(\ell)} \equiv{2^a} \pmod{\ell}$

This post has been edited 1 time. Last edited by 554183, Nov 5, 2021, 2:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megarnie

5551 posts

megarnie

#22 h Feb 6, 2022, 2:28 PM

Y by

ISL marabot solve

This is obvious if $x$ has finitely many digits after the decimal point, because it also implies that $y$ has finitely many digits after the decimal point.

If $x$ has infinitely many digits after the decimal point, then let its period be $k$ . For odd $k$ , this is obvious as $2^n$ cycles $\pmod k$ since $2^{\phi(k)}\equiv 1\pmod k$ . Now consider what happens if $k$ is even. Then let $k=2^l m$ where $m$ is odd. After a certain point, when $n$ exceeds $l$ , $2^n$ will cycle $\pmod k$ . So $y$ is also rational.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bluelinfish

1446 posts

bluelinfish

#23 h Apr 7, 2022, 12:08 AM

Y by

Just a little easy for an N2.

Note that if $x$ is rational, after a certain amount $C$ of decimal places the decimal representation of $x$ is periodic (including possibly all zeroes). Let this period be $P$ . Consider the decimal places of $y$ past $\log_2 C$ . Now observe that for $n$ greater than this quantity the $n$ th decimal place of $y$ is completely determined by $2^n$ modulo $P$ . It is easy to see that $2^n$ modulo $P$ is periodic, thus after $\log_2 C$ decimal places the decimal representation of $y$ is periodic, proving it is rational.

This post has been edited 1 time. Last edited by bluelinfish, Apr 7, 2022, 12:09 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cj13609517288

1879 posts

cj13609517288

#24 h Apr 16, 2022, 8:13 PM

Y by

Because $x$ is rational, at one point, it must start repeating. Let the period of the repeating be $k$ . Let $m$ be the least positive integer $n$ such that the $2^n$ -th digit after the decimal point of $x$ is part of the repeating. We know that at least two of $2^m,2^{m+1},\dots,2^{m+k}$ are equivalent mod $k$ , so let the exponents of those two numbers be $a$ and $b$ . We can see that the $2^{a+1}$ -th and the $2^{b+1}$ -th digits in $x$ are equal and so on, meaning that $y$ now repeats with a period of $b-a$ , meaning that it is rational. QED.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mogmog8

1080 posts

Mogmog8

#25 h Jul 26, 2022, 2:39 AM • 1 Y

Y by centslordm

Suppose $x$ is rational. Notice after some amount of digits which do not repeat, $x$ repeats with period $t.$ It suffices to show this is also the case for $y.$ We claim there exists a constant $k$ such that $2^i\equiv 2^{i+k}\pmod{t}$ for sufficiently large $i.$ Indeed, let $t=2^ab$ where $2\nmid b,$ and suppose $i\ge a.$ Then, there exists $k$ such that $2^k\equiv 1\pmod{b}\implies 2^{k+i-a}\equiv 2^{i-a}\pmod{b}\implies 2^{k+i}\equiv 2^i\pmod{2^ab}.$ Hence, $y$ is also eventually periodic and we are done. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1683 posts

awesomeming327.

#26 h Jul 26, 2022, 7:18 PM

Y by

HUh

If $x$ eventually terminates we are done because $y$ eventually terminates. Otherwise let $x=0.\bar{d_1d_2d_3\dots d_k}.$ Since $2^i$ is periodic mod $k$ we're done because then the digits of $y$ are periodic.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

metricpaper

54 posts

metricpaper

#27 h Aug 24, 2022, 10:10 PM

Y by

Let $x=\Sigma_{i=1}^{\infty} 10^{-i} a_i$ , where for all $i$ , we have $a_i\in \{0,1,\dots,9\}$ . Then $y=\Sigma_{i=1}^{\infty} 10^{-i} a_{2^i}$ . Note that if $x$ is a terminating decimal, then so is $y$ , and then $y$ is automatically rational. Else $x$ is a repeating decimal, so suppose that the digits of $x$ have a period of $r$ , i.e. suppose that if $i\equiv j\pmod{r}$ then $a_i=a_j$ .

Note that $2^i\equiv 2^{i+\phi(r)}\pmod{r}$ for every $i\in \mathbb{Z}_{\geq 0}$ , since $2^\phi(r)\equiv 1\pmod{r}$ by Euler's theorem. So for every $i\equiv j\pmod{\phi(r)}$ , we have $2^i\equiv 2^j\pmod{r}$ , which means that $a_{2^i}=a_{2^j}$ . Therefore the sequence $(a_{2^i})_{i=0}^{\infty}$ is periodic with period $\phi(r)$ , so $y\in \mathbb{Q}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JAnatolGT_00

559 posts

JAnatolGT_00

#28 h Sep 7, 2022, 1:37 PM • 1 Y

Y by PRMOisTheHardestExam

Since $x\in \mathbb{Q}$ sequence of it's digits after the decimal point has period $m$ , starting from some position. Thus for some big $k$ the $k-\text{th}$ digit of $y$ depends on remainder $a_i$ of $2^k$ mod $m$ . But $\left \{ a_i\right \}$ is clearly periodic from some member, implying $y\in \mathbb{Q}.$

This post has been edited 1 time. Last edited by JAnatolGT_00, Sep 7, 2022, 1:37 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SatisfiedMagma

454 posts

SatisfiedMagma

#29 h Dec 12, 2022, 3:41 PM

Y by

Solution: The solution is a casework on whether the decimal expansion of $x$ terminates or not.

Case 1: $x$ terminates in its decimal expansion.

Say $x = 0.a_1a_2\ldots a_k$ where $a_i$ is a digit for $i \in [1,k]$ . Let $\alpha$ be a number such that $2^{\alpha} \le k < 2^{\alpha+1}$ . Observe that that the first $\alpha$ digits of $y$ will be $a_2, a_4, \ldots, a_{2^{\alpha}}$ . Every digit beyond that will be 0. This means $y$ must have a terminating decimal expansion therefore $y$ must be rational as desired.

Case 2: $x$ has a non-terminating decimal expansion.

This is the more interesting part of the problem. It is well-known that digits of a non-terminating decimal expansion are eventually periodic iff it is a rational number. This means digits of $x$ also must be eventually periodic. Therefore $x$ can be written as
$x = 0.a_1a_2\ldots a_k \, \overline{b_1b_2\ldots b_m}$ where again $a_i$ and $b_j$ are digits. Here $a_i$ is non-periodic part and $b_j$ is periodic part. It is easy to see that $m$ is the period of the repeating part. Once more, let $\alpha \in \mathbb{Z}^+$ such that $2^\alpha \le k < 2^{\alpha + 1}$ . One can again determine the first $\alpha$ digits of $y$ as stated in the above case. Say the $(\alpha + 1)$ th digit is some $b_l$ . By basic modular arithmetic, the $(\alpha +2)$ th digit will be $b_h$ where $h = l\cdot 2 + k \pmod{m}$ . The next digit can be generated similarly(a small induction which is skipped). Since we want to show that $y$ is rational, it suffices to show its decimal expansion is also eventually periodic. This boils down to showing there exists distinct $a,b$ such that
$2^al + (2^a-1)k \equiv 2^bl + (2^b-1)k \pmod{m} \iff (l-k) (2^a-2^b) \equiv 0 \pmod{m}$ Now since $2^a$ is periodic modulo $m$ , we are done. $\blacksquare$

Remark. The last congruence is the $a$ th digit after the non-periodic part, therefore the congruence above makes sense.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kamatadu

465 posts

kamatadu

#30 h Jan 21, 2023, 3:38 PM • 3 Y

Y by GeoKing, HoripodoKrishno, Frank25

my first NT from some contest, it's actually time to stop doing just geo, i'm way too numbax T__T

Page 1 Page 2

handwritten solution images attached

This post has been edited 2 times. Last edited by kamatadu, Jan 21, 2023, 3:40 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pinkpig

3761 posts

pinkpig

#31 h Mar 9, 2023, 11:37 PM

Y by

Solution

Someone please proofread because ~~i think~~ this doesn't make sense at all.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathsSolver007

542 posts

MathsSolver007

#32 h Mar 14, 2023, 4:50 PM

Y by

Solution Sketch

This post has been edited 1 time. Last edited by MathsSolver007, Mar 14, 2023, 5:22 PM
Reason: typo!!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8857 posts

HamstPan38825

#33 h Mar 15, 2023, 4:14 AM

Y by

Let the decimal expansion of $x$ repeat with period $k$ . Notice that $\{2^n\}_{n \geq 1}$ is periodic modulo $k$ , so the decimal representation of $y$ repeats too. Thus $y$ is rational.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RedFireTruck

4221 posts

RedFireTruck

#34 h Jun 4, 2023, 9:28 PM

Y by

if $x$ terminates then so does $y$

otherwise, $x$ will eventually repeat with some period $t$ , in which case $y$ will repeat with some period $p | \phi(t)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

huashiliao2020

1292 posts

huashiliao2020

#35 h Aug 22, 2023, 7:07 PM

Y by

storage from a while ago

I'm confused if this is a fakesolve or not...
If x terminates y will terminate. If x is periodic after some number of digits with period $p=2^ij\forall i=v_2p$ , it's well known that $2^n$ is periodic mod j and $2^n\equiv 0\pmod {2^i}$ , hence it is periodic mod p as well. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

793 posts

shendrew7

#36 h Dec 1, 2023, 4:13 AM

Y by

Obviously if $x$ terminates then $y$ must also terminate, making it rational.

Otherwise, $x$ must eventually becomes periodic, suppose with period $k$ . Clearly we can build a period wih Euler's Totient function and CRT on the sequence $\{2^n\} \pmod{k}$ , making $y$ periodic and thus rational.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

potatohunter

16 posts

potatohunter

#37 h Dec 3, 2023, 6:11 AM

Y by

The bulk of the problem is in the following lemma:
Lemma. If $\alpha$ is rational if and only if its decimal representation terminates, or is eventually periodic.
Proof. The $\Longleftarrow$ is standard. We thus show $\implies$ . Let $\alpha = p/q < 1$ (if $p/q > 1$ , just simplify it). Then do long division of $p/q$ . We note that doing this process, we always add $0$ s to the back of our remainder. If it terminates (this happens if the remainder is 0), we are done. Otherwise, to show periodicity, it suffices to show the same remainder will appear twice. This is true by pigeonhole principle, since there are only $q$ possible remainders.

If $x$ terminates, then $y$ also terminates, hence $y$ must be rational. Otherwise, $x$ is eventually periodic. Take this period to be $P$ . Note that $2^{k + \phi(P)} \equiv 2^k \pmod P$ , i.e. $y$ will also be eventually periodic; it must hence be rational.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2513 posts

joshualiu315

#38 h Dec 9, 2023, 4:56 AM

Y by

If the decimal expansion of $x$ terminates, then it is clear that the decimal expansion of $y$ must terminate too, making it rational. If the decimal expansion of $x$ repeats, let the period be $p$ . The sequence $\{2^n\}$ is periodic modulo $p$ , so the decimal expansion of $y$ also repeats, implying $y$ is rational. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Cusofay

85 posts

Cusofay

#39 h Mar 30, 2024, 2:21 PM

Y by

Since $x$ 's digits are $k-$ periodic after some $n$ -th digit , it is trivial that $y$ 's digits will eventually become periodic since $2^i$ is periodic modulo $k$

$\mathbb{Q.E.D.}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ATGY

2502 posts

ATGY

#40 h Jun 20, 2024, 5:53 PM

Y by

Say we have $x$ terminating, having $k$ digits. Consider $2^m > k$ , $2^{m - 1} < k$ . Notice that the $m$ 'th digit of $y$ and after will all be $0$ meaning that $y$ is terminating as well, meaning $y$ is rational.

If $x$ is non-terminating, then it must have a repeating sequence of digits, say of length $k = 2^p \cdot q$ . We essentially want to prove that $2^n$ is periodic modulo $k$ . Notice that $2^{\phi(q)} \equiv 1\mod{q}$ , take large enough $a$ , then we have $2^{a + \phi{q}} \equiv 2^a \cdot 2^{\phi{q}} \equiv 2^a \mod{k}$ , so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

de-Kirschbaum

187 posts

de-Kirschbaum

#41 h Jun 30, 2024, 2:29 PM

Y by

Since $x$ is rational we know that its decimal digits must be eventually periodic, lets say it goes periodic after $t$ digits and the period is of length $k$ . Then lets start at the smallest $d$ such that $2^d \geq t$ , so that's the $d$ -th digit of $y$ . Now there are two cases, if $\gcd(k,2)=1$ then we know that $2^d \equiv 2^{d+\varphi(k)} \mod{k}$ , which means that the $d$ -th digit of $y$ is going to be the same as the $d+\varphi(k)$ -th digit of $y$ , so $y$ is eventually periodic.

If $k=2^em$ where $2^e \mid \mid k$ , then we know that $2^d \equiv 2^{d+\varphi(m)} \mod{m}$ and $2^i \in \{1, 2, 2^2, \cdots, 2^e, 0, \cdots\}$ so we will modify $d$ by $a$ such that $d+a>e$ , then by CRT $2^{d+a+1} \equiv 2^{d+a+\varphi(m)} \mod{k}$ . Thus the $d+a+1$ -th term of $y$ is the same as the $d+a+\varphi(m)$ -th term, which means $y$ is eventually periodic. Thus $y$ must be rational as well.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Likeminded2017

391 posts

Likeminded2017

#42 h Nov 5, 2024, 1:32 AM

Y by

If $x$ is rational iff it repeats every $k$ digits for some $k$ or terminate. If it terminates then $y$ terminates and is rational. If $x$ repeats every $k$ digits then $y$ will eventually repeat as there exists two $2^a$ and $2^b$ with $b-a \le k$ such that $2^a \equiv 2^b \mod k$ because there $k$ total residue classes. This means the decimal digits eventually repeat and $y$ is rational.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

522 posts

Maximilian113

#43 h Dec 14, 2024, 5:43 AM

Y by

Let $p$ be the period of the decimal expansion of $x.$ Clearly, $2^n$ is periodic mod $p,$ meaning the the decimal expansion of $y$ repeats. Therefore, $y$ is rational. QED

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Marcus_Zhang

965 posts

Marcus_Zhang

#44 h Mar 6, 2025, 2:20 PM

Y by

Quick Writeup

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

quantam13

108 posts

quantam13

#45 h Mar 31, 2025, 3:53 AM

Y by

Since the digits of $x$ are eventually periodic with some period $k$ , we get that $y$ 's digits will also be eventually periodic with period $k$ as PHP can easily give that powers of 2 are periodic modulo every integer $k$ . End of story.

Z K Y