A Simple Math Problem

[ssrprotege]

Numbers can be written in different forms besides decimal. Binary, hexadecimal, etc. Another way to say "binary" is that numbers are written in base 2. That said, let's think of this number: 100011, written in base n.

Now, prove that regardless of the value of n, the given number is always a composite number. If you can discover any case that 100011n is a prime, provide the counterexample.

[Monte314]

OK, this sounds really interesting, and I want to make sure I've got it:

You want us to prove that EITHER:

a) for every base n (where 10(binary)<=n<=100011(binary)), when the binary number 100011 is written in that base, the resulting digit string is composite when interpreted as a base 10 number

OR,

b) there is a base n (where 10(binary)<=n<=100011(binary)) so that when the binary number 100011 is written in that base, the resulting digit string is prime when interpreted as a base 10 number.

Is that right? (I don't think I've got it right, because the binary number 100011 expressed in base 100010(binary) is the representation of a prime decimal number. In fact, the number K expressed in base K-1 will always be a prime decimal number.)


(I've got some "story" problems in this area... perhaps I'll post some in the future sometime.)

[AutisticCuckoo]

I interpret the question differently from Monte. Are you asking for proof that n^5+n+1 is always a composite number for any given integer n>1?

[ScottH]

I interpret the question differently from Monte. Are you asking for proof that n^5+n+1 is always a composite number for any given integer n>1?

That's how I understood the question too.

I've verified no primes up to n>1500 (by brute force), but still looking for a proof :-)

[thod]

100011n = n^5 + n + 1. We need to show that for all values of n this can never be prime.

All primes above 2 are odd, thus n^5 is odd and so is n which makes the parity of the equation always odd which doesnt help.

Ofc in base 1 we get 3 which is prime disproving the theory. Can you express a number in base 1?

[ssrprotege]

OK, this sounds really interesting, and I want to make sure I've got it:

You want us to prove that EITHER:

a) for every base n (where 10(binary)<=n<=100011(binary)), when the binary number 100011 is written in that base, the resulting digit string is composite when interpreted as a base 10 number

OR,

b) there is a base n (where 10(binary)<=n<=100011(binary)) so that when the binary number 100011 is written in that base, the resulting digit string is prime when interpreted as a base 10 number.

(I've got some "story" problems in this area... perhaps I'll post some in the future sometime.)

I interpret the question differently from Monte. Are you asking for proof that n^5+n+1 is always a composite number for any given integer n>1?

Monte, AutisticCuckoo understood the question correctly.

That's how I understood the question too.

I've verified no primes up to n>1500 (by brute force), but still looking for a proof :-)

Yes, that's the point. Brute force won't help, as you have to deal with infinity!





ssrprotege added to this post, 1 minutes and 31 seconds later...

100011n = n^5 + n + 1. We need to show that for all values of n this can never be prime.

All primes above 2 are odd, thus n^5 is odd and so is n which makes the parity of the equation always odd which doesn't help.

Ofc in base 1 we get 3 which is prime disproving the theory. Can you express a number in base 1?

Well, I cannot answer that question. But I am sure you know you made a logical mistake.

[Monte314]

Monte, AutisticCuckoo understood the question correctly.



Yes, that's the point. Brute force won't help, as you have to deal with infinity!





ssrprotege added to this post, 1 minutes and 31 seconds later...



Well, I cannot answer that question. But I am sure you know you made a logical mistake.

OK, cool. I'll see what I can come up with. (I love this stuff!)

[ssrprotege]

OK, cool. I'll see what I can come up with. (I love this stuff!)

Good luck! Remember I have high expectations from INTJf's math guru. ;)

[Monte314]

Here is my proof that if N is an integer with |N|>1, then N^5 + N + 1 is composite:


N^5 + N + 1 = (N^2 + N + 1)(N^3 - N^2 + 1)

Since both factors on the right will be integers when N is an integer, it only remains to notice that for |N|>1, both of these factors will have absolute value >1, making the right-hand side a non-trivial factorization of the left, which is, therefore, composite.

Inspection shows that the result is not true for integers N with |N|<2.

[AutisticCuckoo]

Nice, Monte!

Since the premise what that N was a numeric base, the proof only needs to hold for N>1, since you can only express the number 100011 in base 2 or higher (because you need at least two digits: 0 and 1).

[ssrprotege]

Here is my proof that if N is an integer with |N|>1, then N^5 + N + 1 is composite:


N^5 + N + 1 = (N^2 + N + 1)(N^3 - N^2 + 1)

Since both factors on the right will be integers when N is an integer, it only remains to notice that for |N|>1, both of these factors will have absolute value >1, making the right-hand side a non-trivial factorization of the left, which is, therefore, composite.

Inspection shows that the result is not true for integers N with |N|<2.


Nice! Now I must ask you to show how you factored it. It wasn't the easiest expression to be factored; it isn't something like x^2+3x+2=(x+1)(x+2). The proof in the source book's answer key was not only unproductive but also convoluted, whereas I did it in a much simpler way. I want to see whether you discovered "the" simpler way. I expect to see a new approach or mine. I desperately hope you didn't use the "convoluted" method.

Well, since Monte got it, I will explain my method. Monte, was yours similar to mine?


n^5+n+1=n^5+n^4+n^3+n^2+n+1-n^4-n^3-n^2=n^3(n^2+n+1)-n^2(n^2+n+1)+(n^2+n+1)=(n^3-n^2+1)(n^2+n+1)

Because 0 and 1 were used, we know n should be at least larger than 2, . Since neither n^3-n^2+1 nor n^2+n+1 can be 1, we know n^5+n+1, hence 100011n, is a composite number.

QED


If you liked this question, asking your students to solve it won't be too bad. I liked the latest number theory question you posted in the forum.





ssrprotege added to this post, 8 minutes and 6 seconds later...

Nice, Monte!

Since the premise what that N was a numeric base, the proof only needs to hold for N>1, since you can only express the number 100011 in base 2 or higher (because you need at least two digits: 0 and 1).

lol. I was surprised that thod couldn't discover the error. Of course, no offence meant.

[thod]

lol. I was surprised that thod couldn't discover the error. Of course, no offence meant.

Oh I realize that. Yet I am intrigued by the concept of base 1. Since 1^n is always one the whole system of number representations as powers breaks down. The rightmost symbol is always 0 < n since, n = 1 this can only ever be 0 in base 1. The next column is n's then n^2s etc. So 1 base 1 is 10 but it could also be 100 or 1000 and 2 could be 110, 100010 etc. So any number is represented by the number of 1's present and position does not matter. Aliens that counted in base 1 would have no concept of 17 as a number in the sense that we do. To them a number is the marks present with the 0 at the end to indicate that this is a number.

[Monte314]

Well, since Monte got it, I will explain my method. Monte, was yours similar to mine?


I would love to tell you that I took some brilliant direct approach, but I generally solve problems the way a tigress hunts prey: I circle the problem, looking at it from different angles, making short, focused attacks when I see an opening. Sometimes this produces a breakthrough; more often, it generates facts that lead to other openings, and so on, until the whole problem just crumbles.

My (somewhat haphazard) approach:


It was clear from the statement of the problem that if the claim were true, then the expression would have a factorization into polynomials having integer coefficients. (I resisted the temptation to use Eisenstein's Criterion, or Gauss' Lemma)

A little algebra convinced me that there were no linear factors (aN+b), so I knew that it must be the case that:

N^5 + N + 1 = (aN^3 + bN^2 + cN + d)(eN^2 + fN + g)

where the coefficients a, b, c, d, e, f, g are all integers. This immediately implies that the coefficients a, d, e, and g assume the values 1 or -1.

I fiddled around with this manually for a while, but didn't get a result.

I set up a solution method based upon something called the method of undetermined coefficients. This always works in *theory*, but tends to yield non-linear systems of equations that are sometimes harder than the original problem... so I put that aside.

I then evaluated the expression for N=1, 2, 3, 4, 5, and 6, and factored these. Since the N=2 case has two factors, I felt that a way to attack the problem would be to look for two polynomials which would generate the two factors. This would give a factorization of the original expression, and solve the problem.

Here is the table I created:

When N=2 the expression = 35, which has factors 5, 7
When N=3 the expression = 247, which has factors 13, 19
When N=4 the expression = 1029, which has factors 21, 49
When N=5 the expression = 3131, which has factors 31, 101
When N=6 the expression = 7783, which has factors 43, 181

I then said, "OK, it would make the most sense to suppose my smaller factor is given by the second order factor (rather than the third order factor) eN^2 + fN + g, where e & g are 1 or -1.

So, I looked at 43, and noticed that:

43 = 7*7-6 = (6+1)*(6+1)-6 = (N+1)^2 - N.

I applied this rule to 31 and noticed that 31 = (5+1)*(5+1)-5. Then, 21=(4+1)*(4+1)-4, 13=(3+1)*(3+1)-3, and 5=(2+1)*(2+1)-2. In other words, the Nth smaller factor could always be written (N+1)^2 - N = N^2 + N + 1.

Therefore, for the few cases I had checked, e=1, f=1, and g=1 always worked.

I divided N^5 + N + 1 by N^2 + N + 1 and got a cubic result that had integer coefficients... (i.e., it went in evenly).

Voila! I now had a non-trivial factorization in integers of the general form, showing it to be composite.

[ssrprotege]

I would love to tell you that I took some brilliant direct approach, but I generally solve problems the way a tigress hunts prey: I circle the problem, looking at it from different angles, making short, focused attacks when I see an opening. Sometimes this produces a breakthrough; more often, it generates facts that lead to other openings, and so on, until the whole problem just crumbles.

My (somewhat haphazard) approach:


It was clear from the statement of the problem that if the claim were true, then the expression would have a factorization into polynomials having integer coefficients. (I resisted the temptation to use Eisenstein's Criterion, or Gauss' Lemma)

A little algebra convinced me that there were no linear factors (aN+b), so I knew that it must be the case that:

N^5 + N + 1 = (aN^3 + bN^2 + cN + d)(eN^2 + fN + g)

where the coefficients a, b, c, d, e, f, g are all integers. This immediately implies that the coefficients a, d, e, and g assume the values 1 or -1.

I fiddled around with this manually for a while, but didn't get a result.

I set up a solution method based upon something called the method of undetermined coefficients. This always works in *theory*, but tends to yield non-linear systems of equations that are sometimes harder than the original problem... so I put that aside.

I then evaluated the expression for N=1, 2, 3, 4, 5, and 6, and factored these. Since the N=2 case has two factors, I felt that a way to attack the problem would be to look for two polynomials which would generate the two factors. This would give a factorization of the original expression, and solve the problem.

Here is the table I created:

When N=2 the expression = 35, which has factors 5, 7
When N=3 the expression = 247, which has factors 13, 19
When N=4 the expression = 1029, which has factors 21, 49
When N=5 the expression = 3131, which has factors 31, 101
When N=6 the expression = 7783, which has factors 43, 181

I then said, "OK, it would make the most sense to suppose my smaller factor is given by the second order factor (rather than the third order factor) eN^2 + fN + g, where e & g are 1 or -1.

So, I looked at 43, and noticed that:

43 = 7*7-6 = (6+1)*(6+1)-6 = (N+1)^2 - N.

I applied this rule to 31 and noticed that 31 = (5+1)*(5+1)-5. Then, 21=(4+1)*(4+1)-4, 13=(3+1)*(3+1)-3, and 5=(2+1)*(2+1)-2. In other words, the Nth smaller factor could always be written (N+1)^2 - N = N^2 + N + 1.

Therefore, for the few cases I had checked, e=1, f=1, and g=1 always worked.

I divided N^5 + N + 1 by N^2 + N + 1 and got a cubic result that had integer coefficients... (i.e., it went in evenly).

Voila! I now had a non-trivial factorization in integers of the general form, showing it to be composite.


Nice! In general I knew most people would approach the undetermined coefficient method (that was the answer key's "convoluted" method). But I didn't want to deal with too many unknown values, so I quickly discarded that method. Instead, I filled in what was "missing" between n^5 and n, subtracted "missing" terms then factored them. And you did them by finding the patterns between N and one of the factors! Now I know three ways to solve this question. :)