13
$\begingroup$

The complete problem is the following:

You have a set of numbers of the form M = { 7, 77, 777, …, 77…7 (n times) }.

Can it be that you have two disjoint sets A and B such as $A \cup B = M$ have the property that the product of A's elements equals the product of B's elements?

Note: it's from a collection of problems for the 6th grade but I don’t mind of any solution.

$\endgroup$
4
  • 1
    $\begingroup$ Maybe it would be interesting to note that is not true that every element of the set $\{7, 77, 777, 7777, \ldots\}$ is squarefree (i.e., we can take a number formed by justaxposing $7$s $3^n$-times in order to get $3^n$ as a factor). Furthermore, it is possible to get numbers that are divisible by $7$ squared... just take a look at $777777$, which is equal to $3 \cdot 7^2 \cdot 11 \cdot 13 \cdot 37$. $\endgroup$ Commented Jan 7 at 15:57
  • 1
    $\begingroup$ @MarcoRipà I've reached the conclusion that numbers like 777777 having 6k digis have (at least) an additional 7 when being decomposed, but I still haven't managed to do anything about it. That's why I was initially asking how to prove that the product of all numbers from set M cannot be a perfect square - my intuition tells me that P(A) cannot be equal to P(B) where P represents the product of A/B elements. $\endgroup$ Commented Jan 7 at 16:01
  • 1
    $\begingroup$ @IulianSerbanoiu I would start from the divisibility criterion by $7$. Then we can observe that $42=6 \cdot 7$ and this adds one more $7$ to the $6$ $7$s case, so we can repeat the idea stated above for the cases when the number of $7$ is a multiple of $3^n$. It wouldn't be so hard to get a proof. $\endgroup$ Commented Jan 7 at 16:10
  • 2
    $\begingroup$ Dare I ask if the problem statement stipulates that $n > 0$? $\endgroup$
    – kaya3
    Commented Jan 9 at 21:56

3 Answers 3

36
$\begingroup$

I apologize for posting another answer, but apparently everyone, including me, missed a very simple proof why the product is never a square, which is indeed suitable for children: just consider everything modulo $4$. If the number ends in $77$ it is congruent to $1$ modulo $4$, and $7 \equiv 3\pmod 4$, and $3$ is not a square mod $4$.

$\endgroup$
2
  • 4
    $\begingroup$ An even simpler proof: Let's suppose it's possible. The two products are equal, so they are equal modulo 4 as well. 7 is 3 modulo 4, all other numbers are 1 modulo 4 (because they end in 77). Thus one of the products containing 7 is $3\cdot1\cdot1\cdot\ldots=3$ modulo 4, and the other product is $1\cdot1\cdot1\cdot\ldots=1$ modulo 4. This is a contradiction, so it's impossible to have such products. $\endgroup$
    – pts
    Commented Jan 10 at 9:45
  • 1
    $\begingroup$ @pts, now I understand the answer. $\endgroup$
    – dEmigOd
    Commented Jan 10 at 10:48
10
$\begingroup$

I will show that even the product of the first $n-1$ terms of the set is not divisible by the $n$'th term; this is clearly enough since it has to go to one of the subsets. If $n = 1, 2, \ldots , 6$, then you can check it directly. So, assume that $n > 6$.

By Zsigmondy's Theorem $10^n - 1$ has a prime divisor $p$ that does not divide $10^k - 1$ for all $k < n$. I claim that $p > 7$ and that $p$ divides $77\ldots 7$ ($n$ sevens). Indeed, $p$ is clearly not $2$ and not $5$ since $10^n-1$ is coprime to $2$ and $5$. We also know that $p$ is not $3$ and not $7$ because $10^6-1$ is divisible by $3$ and $7$, and we assumed that $n > 6$. So, $p > 7$.

That $p$ divides $77\ldots 7$ ($n$ sevens) is also clear now because it is $7\frac{10^n-1}{9}$ and $p > 7$, so it still divides this number. Similarly, it does not divide any of the numbers $77\ldots 7$ (with $k$ sevens) because, once again, $p > 7$. So, our number does not divide the product of all other numbers because it is divisible by $p$, and all of the other ones aren't.

$\endgroup$
4
  • 1
    $\begingroup$ I don't think this is enough for the previous question, on whether the product can be a perfect square, because it's possible that $v_p(10^n - 1) = 2$. Do you know if Zsigmondy's theorem can be strengthened to require $v_p(a^n - b^n) = 1$? $\endgroup$ Commented Jan 7 at 16:06
  • 1
    $\begingroup$ @CommandMaster indeed, it is not enough, hence why before posting this I asked OP whether he will be satisfied with the answer to the weaker question. $\endgroup$ Commented Jan 7 at 16:07
  • 1
    $\begingroup$ I will try to get from that to a 6th grade level - fingers crossed - I'm starting to dust off my math. $\endgroup$ Commented Jan 7 at 16:10
  • 9
    $\begingroup$ @IulianSerbanoiu if your goal was to get a 6th grade solution, then, more or less by definition, this question would not be acceptable for mathoverflow, in my opinion. $\endgroup$ Commented Jan 7 at 16:12
9
$\begingroup$

A short solution of the original problem. Denote $\underbrace{1\dots 1}_{k\text{ times}}$ by $c_k$. Notice that if $\ell>k$, then $c_\ell=10^{\ell-k}\cdot c_k+c_{{\ell-k}}$. Thus, $\gcd(c_\ell,c_k)=\gcd(c_{\ell-k},c_k)$. Moreover, $k\mid\ell$ clearly implies $c_k\mid c_\ell$. These observations indicate that in general $\gcd(c_\ell,c_k)=c_{\gcd(\ell,k)}$. In particular, if $\ell$ and $k$ are coprime, the so are $c_\ell$ and $c_k$. Now suppose there is a partition $A\sqcup B$ of $\{1,\dots,n\}$ for which

$$\prod_{a\in A}7^ac_a=\prod_{b\in B}7^bc_b.$$

Aiming for a contradiction, notice that by Chebyshev's theorem there exists an odd prime $p$ with $\frac{n}{2}<p<n$. For any $k\in\{1,\dots,n\}\setminus\{p\}$ one has $\gcd(c_p,c_k)=c_{\gcd(p,k)}=1$. WLOG, suppose $p\in A$. Hence $c_p\mid \prod_{b\in B}7^bc_b$. But $c_p$ is coprime with respect to any $c_b$ appearing on the RHS. Hence $c_p$ must divide $\prod_{b\in B}7^b$; in particular, it should be a power of $7$. But the same can be said about any other prime number $q$ between $\frac{n}{2}$ and $n$. There indeed exist two distinct primes $p$ and $q$ in the interval $\left(\frac{n}{2},n\right)$ for moderately large values of $n$ (e.g. $n\geq 40$, see here). They are indeed coprime and so are $c_p$ and $c_q$. Thus the last two numbers cannot be powers of $7$ simultaneously. For small values of $n$ for which there exists precisely one prime $p$ satisfying $\frac{n}{2}<p<n$, one should directly check that $c_p$ is not a power of $7$.

Update Following the comments by fedja and Aleksei Kulikov, the solution can be improved to show that $\prod_{k=1}^n7^kc_k$ is not a perfect square for $n\geq 6$. Assuming the contrary, $\prod_{k=1}^n\frac{c_k}{7^{e_k}}$ should be a perfect square where $e_k$ denotes the exponent of $7$ in the prime factorization of $c_k$. With the prime number $p$ as before, $\frac{c_p}{7^{e_p}}$ is coprime with respect to all other numbers appearing in the product. Hence $\frac{c_p}{7^{e_p}}$ should be a square itself. But that implies $c_p$ is of the form $x^2$ or $7x^2$. The former is impossible since $c_p\equiv 3 \,(\textrm{mod}\ 4)$. As for the latter, $7\nmid c_p$ because $7\mid c_6=111111$ and$\gcd(c_p,c_6)=c_{\gcd(p,6)}=c_1=1$.

$\endgroup$
6
  • 1
    $\begingroup$ Nice solution! There is also a simple reason why $c_p$ is never a power of $7$: it is divisible by $7$ if and only if the number of digits is divisible by $6$, so if $c_p$ is divisible by $7$, it is also divisible by $3$. $\endgroup$
    – fedja
    Commented Jan 7 at 17:17
  • 1
    $\begingroup$ In fact, this can be improved to the solution of the question about the square product! First of all, $c_k$ is divisible by $7$ if and only if $k$ is divisible by $6$, and there aren't many primes divisible by $6$, so in fact Bertrand postulate is enough for your solution. Now, we have to figure out if $c_p$ can be a square and, for a very stupid reason, it can not: $c_p$ is always $3$ mod $4$. $\endgroup$ Commented Jan 7 at 17:18
  • 1
    $\begingroup$ @fedja argh, you beat me by 15 seconds :) $\endgroup$ Commented Jan 7 at 17:18
  • 1
    $\begingroup$ @AlekseiKulikov "Now, we have to figure out if $c_p$ can be a square" Erm... I would rather say not a power of $7$ times a square. And that seems a bit less trivial, doesn't it? $\endgroup$
    – fedja
    Commented Jan 7 at 17:23
  • 1
    $\begingroup$ @fedja I just said that $c_p$ is not divisible by $7$ because $p$ is not divisible by $6$, being, ummm, prime... $\endgroup$ Commented Jan 7 at 17:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .