[HN Gopher] Where do those undergraduate divisibility problems c...
___________________________________________________________________
Where do those undergraduate divisibility problems come from?
Author : mathgenius
Score : 157 points
Date : 2025-01-20 09:41 UTC (1 days ago)
(HTM) web link (grossack.site)
(TXT) w3m dump (grossack.site)
| jmount wrote:
| More on integer valued polynomials:
| https://cameroncounts.wordpress.com/2017/01/31/polynomials-t...
| svat wrote:
| That blog post is specifically about the question about whether
| a polynomial taking integer values on positive integers (or any
| sufficiently large subset thereof) necessarily is an integer-
| valued polynomial (the answer is yes).
|
| The OP blog post here actually links to / points out there's an
| Wikipedia article on integer-valued polynomials:
| https://en.wikipedia.org/wiki/Integer-valued_polynomial
|
| Among other things, as mentioned, "every integer-valued
| polynomial can be written as an integer linear combination of
| binomial coefficients" [in exactly one way].
|
| The conjecture in the OP post, that every polynomial everywhere
| divisible by k counts {something}, is intriguing, and I
| wouldn't be surprised if it were true.
| dang wrote:
| [stub for offtopicness]
| mjd wrote:
| I feel silly saying this, but I wish the author would use more
| periods and fewer exclamation marks.
| tromp wrote:
| Elaine Benes would be proud of their writing...
| leetcrew wrote:
| I was in the pool!
| gazchop wrote:
| Oh this is nothing. One of my colleagues does that and adds
| random colour changes, underlines and font face changes. It's
| like working with a serial killer.
| gota wrote:
| Maybe he was a teenager on IRC in the late 90s or early 00s
| and decided to never change
|
| Thinking about it I guess MSN messenger and My Space also
| allowed/encouraged font shenanigans? My memory falters
| andrepd wrote:
| Ahh. I honestly miss that amount of self-expression,
| garish as it was. Or rather, I intensely dislike the
| mono-culture where every vertical video with one-word
| subtitles looks the same.
| amne wrote:
| You're the second commenter, so far, to mention exclamation
| marks. What do they mean to you that would bother you so much
| to point it out, or anyone for that matter? I haven't even
| noticed them until I read the comments here on hn.
| micaeked wrote:
| Not gp, but I feel similarly. For me, I can't help read it
| with emphasis. As in, the voice in my head gets all fancy
| in an annoying way. If you imagine someone in person
| reading it out-loud with exaggerated emphasis, that's what
| it feels like. Same thing with comic books for me, the
| sprinkled bolded words in dialog are really grating.
| Etheryte wrote:
| To me it's fairly similar to someone making excessive use
| of CAPS LOCK. It can be used as a stylistic choice at
| times, but use it TOO MUCH and it just becomes DISTRACTING.
| Minor49er wrote:
| I DON'T SEE A PROBLEM WITH THIS EITHER! BUT I EMPATHIZE! I
| GET COMMENTS FROM PEOPLE SAYING THAT I'M SOMEHOW YELLING AT
| THEM ALL THE TIME BUT I'M ACTUALLY SITTING IN SILENCE,
| TYPING QUIETLY ON A MEMBRANE KEYBOARD! LOL???
| np_tedious wrote:
| Well I was curious, but there's a lot there I didn't understand.
| Apparently I'm good enough at math to do the proofs, but not to
| write the exercises.
|
| Exercise left to the reader:
|
| Prove 7*n^3 + n is divisible by 2
| abnry wrote:
| 7 _n^3 +n (mod 2) = 1_ n^3 + n = n + n = 2*n = 0*n = 0
| BurningFrog wrote:
| 7*n^3 is even when n is even and odd otherwise.
|
| odd + odd is even, as is even + even.
| Spivak wrote:
| The easy way of seeing the first part is to do the prime
| factorization. The 7 doesn't matter since it's prime. If n
| has a 2 in its factorization it now has 2^3. But if it
| doesn't have a 2 it won't suddenly acquire one.
|
| All the symbol soup proofs aren't wrong but I don't think
| they satisfyingly explain the why.
| thaumasiotes wrote:
| All of these "always divisible by n" proofs are asking you
| to solve them case by case in modular arithmetic.
|
| For divisibility by two, there are only two cases. So if n
| is 1, then n3 is 1, and if n is 0, n3 is 0. 0+0 = 0; 1+1 =
| 0; and this completes the proof.
|
| I am not actually sure that doing a prime factorization on
| 7n3 for unknown n is easier than knowing that 13 = 1.
| crabbone wrote:
| I vote this the best proof. All you need to know to
| understand it is to know how multiplication, addition and
| exponentiation works. You could probably show this to a child
| in a sixth grade or so, and have them understand it. This is
| really good!
| cherryteastain wrote:
| Given p(n) = 7n^3 + n:
|
| If n is even, we can choose some m such that n = 2m, and p(n) =
| p(2m) = 7 * 8m^3 + 2m = 2 * (7 * 4m^3 + m), which is divisible
| by 2 since we could factor out the 2 at the start.
|
| If n is odd, similarly we can say n = 2m + 1. p(2m) = 7 * (2m +
| 1)^3 + (2m + 1) = 56m^3 + 84m^2 + 44m + 8 = 2 * (28m^3 + 42m^2
| + 22m + 4), which is also divisible by 2 per the 2 at the
| start.
| MichaelRo wrote:
| >> Apparently I'm good enough at math to do the proofs, but not
| to write the exercises.
|
| Took a look on it, seems like a highly particular / specialized
| area of mathematics. It's like computer science, can't know
| them all. If you work all day with some area, say compilers or
| databases or financial software or what else, you'd be a whizz
| at it while it's unreasonable to expect someone from a
| different domain be able of more than a superficial
| understanding of what you write.
|
| I'm pretty good at math but like with computers, I don't have
| the compulsion to dive deep into an unfamiliar domain just for
| the sake of it. So commenting on the article: cool, now I know
| how these problems are formed and in the very unlikely domain
| I'll need to produce one, I know where to look. Likely this
| will never happen, though.
| dleeftink wrote:
| > seems like a highly particular / specialized area of
| mathematics. It's like computer science, can't know them all
|
| As a non-mathy, I'm interested in whether the _idea_ that
| being good /able to provide proofs in one area, automagically
| makes one proficient in another is customary in the field or
| rejected quite early on when choosing a math specialisation?
| svat wrote:
| It is not typical that being good in one area of
| mathematics makes one proficient in another -- mathematics
| has a lot of depth, and to reach the frontier in any
| specialization requires years of study. However:
|
| - There are skills that carry over; these are usually known
| by the name "mathematical maturity" https://en.wikipedia.or
| g/w/index.php?title=Mathematical_matu...
|
| - There is a story/legend told about Erdos, where he was so
| good at problem-solving/proofs that he once solved a
| problem in another area after asking for the definitions of
| the terms in the problem. (The fact that this story is told
| illustrates that it is not commonplace.)
| MichaelRo wrote:
| Well there is common stuff that one must be familiar with
| to be proficient and marginal stuff that you can get by
| without knowing because chances is you're not going to need
| it.
|
| Like take for instance financial mathematics where I had
| some special interest, it's totally oblivious to areas such
| as geometry or number theory. I never had to figure out if
| a polynomial is divisible by 6 for instance :)
|
| Like computer science, there's the common algorithms stuff
| but being an expert in web development doesn't help you
| much in writing high frequency trading server code, and the
| other way around.
| dh2022 wrote:
| n = 0 or 1 modulo 2. So we have to check out only two cases
| module 2, and these cases trivial. To prove the problem note
| that 6 = 2 * 3 and then is trivial to see that the polynomial
| is=0 modulo 2 if n=0,1 modulo 6and then check it is =0 modulo 3
| for n=0,1,2 modulo 3 and you are done.
| deruta wrote:
| And a proof by "counting _something_ ":
|
| 1 + 2 + ... + n = n(n+1)/2
|
| 2 divides n(n+1), n(n+1) = 2m
|
| 7 * n^3 + n =
|
| 2*(3*n^3 + n) + n^3 - n =
|
| 2*(3*n^3 + n) + n(n+1)(n-1) =
|
| 2*(3*n^3 + n + m(n-1))
| svat wrote:
| > _but not to write the exercises_
|
| As the post mentions in passing, the integer-valued polynomials
| are completely characterized by the property that when written
| as a sum of {c_i (x choose i)}, all the coefficients c_i are
| integers. I imagine this is where most of the exercises
| _actually_ come from. For example, using [3 1 4 1 5 9], the
| polynomial {3 + 1*x + 4*x(x-1) /2 + 1*x(x-1)(x-2)/6 +
| 5*x(x-1)(x-2)(x-3)/24 + 9*x(x-1)(x-2)(x-3)(x-4)/120} simplifies
| to 1/120 (9x^5 - 65x^4 + 185x^3 + 5x^2 - 14x + 360), so you
| could use it to generate exercises like:
|
| - Prove that 9x^5 - 65x^4 + 185x^3 + 5x^2 - 14x + 360 is always
| a multiple of 120
|
| (or 5, or any divisor of 120).
| t43562 wrote:
| My daily dose of inferiority: done. :-) Perfect sentences which
| are complete gobblede-gook to me.
| agnishom wrote:
| TLDR Summary:
|
| There is a genre of undergraduate polynomial divisibility
| problems which look like this: Show that f(n) is divisible by
| some integer k.
|
| These problems often appear to be (elementary) number theory
| problems. However, often there is a rather elegant proof
| associated with them which is based on combinatorics.
|
| The crux of this proof is that the polynomial counts the number
| of equivalence classes of a certain kind.
|
| This is closely related to
| https://en.wikipedia.org/wiki/Burnside%27s_lemma
|
| The question at the end of the post is whether _all_ such
| problems must come this way
| daef wrote:
| i couldnt come up with a proof for the initial problem
| (n^6+n^3+2n^2 is a multiple of 6 for every n)
|
| because it's not true (simply insert 1, 2, 4 or 5)
| goldencoralefan wrote:
| You're missing a term: n^6+n^3+2n^2+2n
| nh23423fefe wrote:
| i just computed the solution mod 2 and mod 3 a la chinese
| remainder theorem
|
| the polynomial is =0 mod2 and =0 mod3 so its =0 mod6
|
| n^6 + n^3 + 2n^2 + 2n (mod 2) = n^6 + n^3 + 0 + 0 = n^3(n^3+1) =
| 0*1 or 1*0 = 0
|
| because consecutive numbers are even then odd then even ....
|
| for mod3 you can make a table
|
| you could also factor the polynomial and see the solution easily
|
| n(n+1)(n^2-2n+2)(n^2+n+1)
___________________________________________________________________
(page generated 2025-01-21 23:03 UTC)