Number theory question I don’t understand at all

[Levido]

Sorry for the late replies everyone, for some reason I stopped receiving email notifications and assumed the thread had died. All your effort and enthusiasm is really encouraging for me

So double entry bookkeeping is about finding errors…

Thanks for thisI’m going to bring it up with an accountant when I get back from travels. Nice but of maths history.

Upon reflection, the proof may be by infinite descent, which is sort of induction combined with contradiction.

The book as my taught me that yet but it is a double star problem so it’s fine if I can’t tackle it until I return to it having done more work. I’m not sure if it counts as “cheating” to google what the structure of that proof is or if I should come up with it myself? I know induction and contradiction so I’m guessing the inductive step is just a contradiction so it must work for n+1. I’m still not sure how I get around 11,22 etc as that goes against what I know about induction, to say it’s true for n+1 but in some cases n+2?

 

[Levido]

Jeff thanks for rewording the question more clearly, and also for a hint about it. This answers my problems before with induction! I now get how I can solve it. I’ll be honest this is a hobby I’m keeping up during my travels so I hadn’t made much progress on this problem, so this is very useful for me

Again, I have not worked this out, but here is a hint…

 

[Levido]

That's worth considering; did you consider it?

It turns out not to matter; 10 - 1 = 9, which is still composite. (But yes, 01 definitely means 1.)

If you found that that case didn't work, then you would want to reword the problem. (For instance, this wouldn't work in base 2, where 10 - 1 = 1, which is not composite!)

@Levido: By the way, the whole idea is simple if you know "casting out nines", but otherwise can be hard to talk about without using modular arithmetic. Since you call it number theory, perhaps you know both? What topics have been covered so far?

[This answer was delayed an hour while I was locked out of the site.]

I actually am aware of modular arithmetic a little, did it during maths a level. Topics wise the book is exactly as you suggested (great research I’m shocked) ,

 

[Levido]

That was a good hint. I've managed to show it, but don't want to hijack the OP's thread. I'll leave the OP a hint:

Spoiler: Hint

Look at divisibility by 9

This takes care where n has 1 digit and the one where n includes 0's.

Thanks, appreciated, I like that you’ve solved it already!

 

[Levido]

Thanks for all your effort. I hope it didn’t take too long to find the book in hindsight I should have included it in the question to save you the trouble.

That's how I saw it at first; but clearly they mean "another" permutation, since the difference 0 is not a composite. If we take it that way, then single digits are excluded. Another instance of poor wording.

@Levido, I located the problem in the book you must be reading:

The Mathematical Olympiad Handbook

Begun in Hungary in the nineteenth century, Mathematical Olympiads are now held for high school students throughout the world. They feature problems which, though they require only high school mathematics, seem very difficult because they are unpredictable and have no obvious starting point...

www.google.com

I see that a couple pages earlier it talked about some related examples; but it doesn't look like they've taught enough to do a genuine proof. I imagine they want just some explanation. I haven't read much of it, though.

They do want a genuine proof but they don’t expect you to be able to do it if you’ve only just started reading their book. I know the problems you’re referring to and the link is there definitely. I’ll give it a good try once I’ve replied but if I can’t I’ll probably just come back to it in a month or so

 

[Levido]

Thanks for all your help everyone

 

[Levido]

I’ve finished my work on this question, I haven’t written my proof out neatly though I can if anyone is particularly interested, I have a long journey ahead of me today and might find your thoughts helpful. I tend to over prove something by explaining things where I don’t need to and need to learn to kick that habit before uni

 

[JeffM]

I’ve finished my work on this question, I haven’t written my proof out neatly though I can if anyone is particularly interested, I have a long journey ahead of me today and might find your thoughts helpful. I tend to over prove something by explaining things where I don’t need to and need to learn to kick that habit before uni

I’d be interested. I might see whether I can do the proof I suggested and then see how it compres with yours.

 

[Dr.Peterson]

(great research I’m shocked) ,

Thanks for all your effort. I hope it didn’t take too long to find the book in hindsight I should have included it in the question to save you the trouble.

It wasn't hard, actually, nor what I would call research. I just sometimes search for a unique phrase in a problem to see if it happens to be discussed elsewhere, or to check whether it was copied correctly, or as in this case to see if there might be any context. I was surprised to find just one hit!

But generally, the more context you can give when you ask a question, the more quickly we can get to giving useful help. We still don't know, for instance, whether you are just reading this book on your own, or as part of a class with someone to direct you.

And we will be interested to see how you attack the proof, and to help if there's anything that could use improvement.

 

[JeffM]

Here is a generalization of the problem and a sketch of the proof

[math]\text {GIVEN that (I) “digits” are to base } \phi \ge 2,\\ \text {(II) the“starting string“ consists of a sequence of } \theta \text { digits,}\\ \text {(III) } n \text { is the integer represented by the starting string interpreted as a numeral in base } \phi, \text { and} \\ \text {(IV) } m \text { is any integer represented by a permutation of the starting string interpreted as a numeral in base } \phi,\\ \text {PROVE that } (\phi - 1) \ | \ (n - m) \text { for any positive integer value of } \theta.[/math]
Now for the sketch.

Spoiler

Lemma 1 is trivial. Regardless of the value of [imath]\theta[/imath], if every digit in the starting string is the same, then the only permutation is the identity permutation, which entails m = n. Thus, n - m = 0, and [imath]( \phi - 1)[/imath] divides zero evenly because every number other than zero divides zero evenly.

Corollary 1a. The proposition is true if [imath]\theta[/imath] = 1 because a string with only one digit has no permutation except the identity permutation.

Corollary 1b. There exists at least one integer [imath]\ge[/imath] 1 for which the proposition is true. Let k be an arbitrary one of those integers. In other words, given a starting string of k digits, the difference between the number represented by that string and the number represented by any permutation of that string is evenly divisible by [imath](\phi - 1).[/imath]

Now we consider the case where [imath]\theta[/imath] = k + 1 [imath]\ge[/imath] 2. Obviously, if all (k + 1) digits are the same, Lemma 1 applies. So we restrict attention to those cases where at least two digits differ. That entails that one digit in the starting string differs from the high order digit in the starting string. We start with another special case, namely permutations where the high order digit stays the same, to get Lemma 2.

[math]n = a_1 * \phi^{\{(k+1)-1} + \sum_{i=1}^k a_{i+1}^k * \phi^{(k-i)} = a_1 \phi^k + b.\\ m = a_1 \phi^k + c, \text { where } c \text { is represented by an arbitrary permutation of the string representing } b.\\ (n - m) = (a_1 \phi^k + b) - (a_1 * \phi^k + c) = b - c.\\ b \text { is represented by a string of } k \text {digits, and } c \text { is represented by a permutation of } b.\\ \therefore \ \exists \text { integer } j \text { such that } (b - c) = ( \phi - 1) * j \text { by Lemma 2.}\\ \therefore n - m = b - c \implies n - m = (\phi - 1) * j \implies\\ (\phi - 1) \ | \ (n - m) \ \because \ j \text { is an integer.}[/math]
Lemma 2 does not directly help us because it covers only those permutations that do not affect the high order digit. So let’s consider another special case, namely one where the permutation leaves in their original position all digits in the starting string except the high order digit and one arbitrary digit that differs from the high order digit. In short, we are considering the special case where the permutation only swaps the high order digit and one digit of a different value. We do not know where this arbitrary different digit may lie in the string so we say it is in the wth position going left to right. All we know is that w is an integer and that 1 < w < k+2. This gives us Lemma 3.

[math]n = \sum_{i=1}^{k+1} a_i \phi^{\{(k +1)-i\}} \implies\\ m = n + (a_w \phi^k - a_1 \phi^k) + (a_1 \phi^{\{(k+1)-w\}} - a_w \phi^{\{(k+1)-w\}}) = n + (a_w - a_1)- a_w)((\phi^k - \phi^{\{(k+1)-w\}}) = \\ n + (\phi^{(w+1)} - 1) * \phi^{\{(k+1)-w\}}(a_w - a_1) = n + (\phi^{(w+1)} - 1^{(w+1)}) * \text {an integer} = \\ n + (\phi - 1) * \left ( \sum_{i=1}^w \phi^{\{(w+1)-i\}} \right ) * \text {an integer} = n + (\phi - 1) * \text {an integer}.\\ \therefore \ n - m = n - n - (\phi - 1) * \text {an integer } = (\phi - 1) * \text {an integer} \implies (\phi - 1) \ | \ (n - m). [/math]
Once again, Lemma 3 does not get us home. We have dealt with all permutations that leave the high order digit alone. And we have dealt with any permutation that swaps the high order digit and a single digit that differs from the high order digit but is otherwise arbitrary. Let’s name as p an arbitrary example of one of those permutations of n. Now leaving the high order digit of p alone, let q be an arbitrary permutation of the low order digits of p. This gets us Lemma 4.

[math]\exists \text { integer } u \text { such that } n - p = (\phi - 1) u \text { by Lemma 3.}\\ \exists \text { integer } v \text { such that } p - q = (\phi - 1) v \text { by Lemma 2.}\\ n - q = n - p + p - q = (n - p) + (p - q) = (\phi - 1)u + (\phi - 1)v = (\phi - 1)(u + v).\\ \therefore \ (\phi - 1) \ | \ (n - q). [/math]
But lemmas 2 and 4 cover all the permutations possible in a string of k+1 digits.

Therefore, by induction, the proposition is true for all positive [imath]\theta[/imath]. Q.E.D. (Well, Q.E.D. unless I made some idiotic blunder.)

Long journey, but it is interesting that the result is a consequence of a place-value system of notation rather than some property peculiar to just some numbers like ten.

Nice little problem.

 

[Dr.Peterson]

Long journey, but it is interesting that the result is a consequence of a place-value system of notation rather than some property peculiar to just some numbers like ten.

It's interesting that the original problem is dependent on the base:

​

In, say, base 12, the generalization would be that [imath]11 | (n-m)[/imath] for any two (different) permutations of the same digits; but then [imath]n-m[/imath] will not be composite when it is (as will frequently happen) exactly equal to 11. But in base 10, since 9 is itself composite, we don't have that issue. The only case in base 10 where [imath]n-m[/imath] is not composite is when [imath]n=m[/imath], so that [imath]n-m = 0[/imath], which is the reason I just added the word "different". This is the twist that most interested me from the start; in particular, I was curious how they expected a student to realize that the underlying fact is related to 9, which was only obvious to me because I already knew the underlying fact. (Or is there another approach they had in mind?)

 

[JeffM]

It's interesting that the original problem is dependent on the base:

View attachment 33585​

In, say, base 12, the generalization would be that [imath]11 | (n-m)[/imath] for any two (different) permutations of the same digits; but then [imath]n-m[/imath] will not be composite when it is (as will frequently happen) exactly equal to 11. But in base 10, since 9 is itself composite, we don't have that issue. The only case in base 10 where [imath]n-m[/imath] is not composite is when [imath]n=m[/imath], so that [imath]n-m = 0[/imath], which is the reason I just added the word "different". This is the twist that most interested me from the start; in particular, I was curious how they expected a student to realize that the underlying fact is related to 9, which was only obvious to me because I already knew the underlying fact. (Or is there another approach they had in mind?)

I think in my restatement I avoided the problem you mentioned by using the ”divides evenly into” symbol rather than “composite.”

Also they made the problem harder by leaving open what the divisor might be.

 

[Dr.Peterson]

I think in my restatement I avoided the problem you mentioned by using the ”divides evenly into” symbol rather than “composite.”

Also they made the problem harder by leaving open what the divisor might be.

Exactly.

 

[AvgStudent]

Since Jeff posted his solution above, I think I can share mine.

Using the fact that if the sum of the digits is divisible by 9, then the number itself is divisible by 9.
Let [imath]n[/imath] be any positive integer and [imath]S(n)[/imath] be the sum of digits, then we have [imath]n \equiv S(n) \text{ mod }9.[/imath]
Similarly, let [imath]n^*[/imath] be a permutation of [imath]n \implies S(n)=S(n^*)[/imath]
Taking the difference [imath]n-n^* \equiv S(n)-S(n^*) \equiv 0 \text{ mod }9[/imath]
Since the difference is divisible by 9 and 9 is a composite, therefore [imath]n-n^*[/imath] is a composite number.