The infinite periodic fractions ab and cd with (a,b)=(c,d)=1 are such that every finite block of digits in the first fraction after the decimal point appears in the second fraction as well (again after the decimal point). Show that b=d.
Problem
Source: St. Petersburg 2023 11.3
Tags: number theory
starchan
12.08.2023 23:36
Let the decimal parts of a/b and c/d look like A¯B and C¯D respectively, for some strings A,B,C,D with character set {0,1,…,9}.
Further, we make the assumptions that B,D have the smallest possible period call them m,n and that A,C have the shortest possible length for that period (i.e. the last character of A (C) cannot be merged into the periodic part ¯B (¯D)). Consider the string B|C|+|D|. It appears in A¯B, thus it appears in C¯D as well. Since the suffix B|D| could not possibly intersect with C due to |B|⋅|C|≥|C|, it follows that B|D| can be found in D∞. In particular, we obtain that for some cyclic shift D′ of D, we have D′|B|=B|D′| forcing that B,D are cyclic shifts of each other and that |B|=|D| (they must have the same period).
Replacing C with a slightly larger string now if necessary, we assume D=B. Thus every finite substring from A¯B is found in C¯B. Define k=|C| and n=|B| for ease of notation. We aim to show now that A is a suffix of C. If A is empty, we are already done, so assume this is not the case. We may assume |C|>0 by adding a D if necessary.
Consider the strings ABi for positive integers i. Suppose the ith such string is found in C¯B from the xith position onward.
Claim: We have xi>k for finitely many i.
Proof:
Assuming otherwise, suppose that xi>k for infinitely many k, so that ABi exists in B∞ for infinitely many i. Some imod repeats infinitely often, fix such a residue r and remark that due to periodicity it follows that AB_1B_2\dots B_r B^{\infty} exists in B^{\infty}. But then it follows that A completely extends into B, a contradiction.
It follows that x_i \in \{1, 2, \dots, k\} for large enough i. Therefore some x_i repeats infinitely often, fix such an x_i and observe that this then implies that A agrees with C_{x_i}C_{x_i+1}\dots C_k B_1 B_2 \dots B_{u} for some positive integer u. Since infinitely many i are obtained by extending this very string, it follows that u = 0, otherwise B would have a smaller period, or A could be introduced into it. This shows that A is a suffix of C. Let \ell = |C|-|A| now and remark that \frac{a}{b} - \frac{10^{\ell}c}{d} is an integer, and thus b \mid d. Repeating this argument from the other side, we obtain that d \mid b, forcing b = d as required.
[edit] @below, thanks for clearing that part up.
a_507_bc
13.08.2023 00:10
I checked the statement again and I didn't find any mistake. Probably the intended meaning is that the same thing should hold for the second fraction as well, so repeating the same argument which you used will show that b=d.