Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Professional Help Needed-Elementary Number Theory

  1. Aug 31, 2012 #1
    Professional Help Needed--Elementary Number Theory

    I will preface this by saying that I have no formal training in Mathematics. I've taken Calc 1 and a couple of Symbolic Logic classes. Forgive me if I butchered any terminology. However, this has been bugging me for a while, and I would like to know if anyone knows anything about this.

    There seems to be a predictable pattern in the gaps between successive terms in series with prime exponents. This has been known for x^2 for a long time.


    x^1== +1
    x^2 == 2x+1

    x^3 == [(x^2+x)(3)] +1

    1+ (1^2+1) (3) +1 = 8
    8 + (2^2+2) (3) +1 = 27
    27 + (3^2+3) (3) +1= 64 ...

    x^5== [(x^2+x)(x^2+x+1)(5)]+1

    1+[(1^2+1)(1^2+1+1)(5)]+1=32
    32 + (2^2+2)(2^2+2+1)(5)+1=243
    243+(3^2+3)(3^2+3+1)(5)+1=1024...


    x^7 = {(x^2 + x) (x^2 + x + 1)^2 (7)} + 1

    x^11 = {(x^2 + x) (x^2 + x +1) ((x^2 + x)^2 + (x^2 + x + 1)^3) (11)} + 1


    x^13 = {(x^2 + x) (x^2 + x + 1)^2 (2 (x^2 + x)^2 + (x^2 + x + 1)^3) (13)} + 1

    I have Mathematica notebooks with the computations for x^7,x^11, and x^13, verifying this up to x=100 and each series gap between successive members follows the pattern. However at x^17, I ran out of steam and cognitive resources. Prime factoring the [[gap term] -1] is how I started looking at the other series, and there is some frustratingly periodic behavior in the prime factors. Twin prime exponents are also connected in some way, but I cannot figure it out.

    I have no idea what this means, if anything at all.
     
  2. jcsd
  3. Aug 31, 2012 #2
    Re: Professional Help Needed--Elementary Number Theory

    Your discovery is based upon the known fact that the coefficients for the binomial (x+1) raised to a prime power P are each divisible by P except the coefficients of x^p and 1. Try searching for the terms "binomial coefficients" and "primes" to see how to prove this.

    P.S. you said the verified your expressions in x by checking individual values in x, say from 1 to 100. The correct use of power of algebra would be to multiply the products, group like terms, and to verify the resulting expression using Pascal's Triangle. I would think this could be done using Mathematica functions. Try asking for help with this in a Mathematica User's group. This would save a lot of computation.

    P.P.S. It appears that you meant to use == instead of = for the expressions for x^7, x^11 and x^13. Your Terminology is unclear. The expressions on the right seem to be (x+1)^n - x^n. In other words you meant to write: (x+1)^n mod x^n == the expression on the right.
     
    Last edited: Aug 31, 2012
  4. Aug 31, 2012 #3
    Re: Professional Help Needed--Elementary Number Theory

    I'm a little lost when it comes to the binomial coefficients. But there are also some other interesting characteristics of the gap term. The sum of the even numbers (x^2+x) and the partial sums of the octahedral numbers also shows up as factors in sequence. .[/PLAIN] [Broken]

    Is that the issue then? Does the binomial theorem explain this and if I understood the binomial theorem would I understand why x^p series behave this way?
     
    Last edited by a moderator: May 6, 2017
  5. Sep 1, 2012 #4
    Re: Professional Help Needed--Elementary Number Theory

    I emailed a Mathematician who started a relatively successful website devoted to Math and Integers about this, and this was his reply. I am not sure if this explains my original question, as Pascal's Triangle would account for the P factor in the gap, but the P is only one part of the functions.

    I am also a little confused on the Maple program that was used, as you can see below, the outputs the Mathematician returned to me use composite exponents that increase (x^6,x^5, etc) whereas the initial functions only use x^2 and x^3. Can someone explain what he is talking about?


    Dear Gordon, Thanks for that message.
    What makes this work is an old theorem of
    Lucas, that says that if p is a prime, every term in
    the p-th row of Pascal's triangle (except the 1's at the ends) is
    divisible by p.

    To do this algebraically, - which is what you are doing -
    we can take (x+1)^p, subtract x^p and 1, and then
    what is left will be divisible by p and we can try to
    factor it.

    Here I will do that in Maple:

    > f:=n->lprint(factor((x+1)^n-x^n-1));

    > f(2);
    2*x

    > f(3);
    3*x*(1+x)

    > f(5);
    5*x*(1+x)*(x^2+x+1)

    > f(7);
    7*x*(1+x)*(x^2+x+1)^2

    > f(11);
    11*x*(1+x)*(x^2+x+1)*(x^6+3*x^5+7*x^4+9*x^3+7*x^2+3*x+1)
    > f(13);
    13*x*(1+x)*(x^6+3*x^5+8*x^4+11*x^3+8*x^2+3*x+1)*(x^2+x+1)^2
    > f(17);
    17*x*(1+x)*(x^2+x+1)*(x^12+6*x^11+26*x^10+75*x^9+156*x^8+240*x^7+277*x^6+240*x^5+156*x^4+75*x^3+26*x^2+6*x+1)

    > f(19);
    19*x*(1+x)*(x^12+6*x^11+28*x^10+85*x^9+184*x^8+292*x^7+341*x^6+292*x^5+184*x^4+85*x^3+28*x^2+6*x+1)*(x^2+x+1)^2

    > f(23);
    23*x*(1+x)*(x^2+x+1)*(x^18+9*x^17+57*x^16+252*x^15+836*x^14+2156*x^13+4423*x^12+7324*x^11+9880*x^10+10911*x^9+9880*x^8+7324*x^7+4423*x^6+2156*x^5+836*x^4+252*x^3+57*x^2+9*x+1)

    Further simplifications get trickier, as you noticed.

    Do you know the book "Concrete Mathematics" by Graham, Knuth et al.? The discussion of Pascal's triangle there
    and of the properties of binomial coefficients are relevant. It is also
    great fun to read.

    Best regards



    My reply:

    Dear XXXX,

    Thanks for your prompt and thoughtful reply. I will look into the book, it sounds very interesting. I was looking over the Maple outputs, and comparing it to the initials functions to see where they went wrong, because there seemed to be a discrepancy after x^7. I know you are probably busy, but I can't figure out why the Maple output has x^n (n from 1 to 6), when the erroneous function is merely squares and cubes.




    x^11 = {(x^2 + x) (x^2 + x +1) ((x^2 + x)^2 + (x^2 + x + 1)^3) (11)} + 1


    > f(11);
    11*x*(1+x)*(x^2+x+1)*(x^6+3*x^5+7*x^4+9*x^3+7*x^2+3*x+1)

    Thanks,

    Gordon


    I am just getting more confused the more people I ask.
     
  6. Sep 1, 2012 #5
    Re: Professional Help Needed--Elementary Number Theory


    Keep at it, eventually everything will become clear. Based upon your work thus far, your not too far from an understanding of this topic. The maple program is somewhat like Mathematica. Basically it defines a function f(n) as equal to the expansion of (x+1)^n - x^n -1 in the format of a product of polynominal factors and P*x. The reason you see terms such as x^6 ... where you have merely squares and cubes is that you had the expression in a different format. You will only see a term such as x^6 where the n in f(n) is greater than 6, so there is no contradiction.
     
  7. Sep 1, 2012 #6
    Re: Professional Help Needed--Elementary Number Theory

    It's not just Pascal's Triangle that evidences such periodic behavior modulo p. All manner of recursively defined triangles demonstrate such behavior, from the Stirling 1 and 2 Triangles to the Eulerian Triangle to the Bernoulli Triangle and beyond.

    I don't know the theorem that would apply, but the patterns are more than apparent with a little trial and error.

    - AC

    P.S. Ramsey 2879, are you familiar with a general theorem that generalizes Lucas' therorem re: Pascal's Triangle to other recursively defined triangles?
     
  8. Sep 2, 2012 #7
    Re: Professional Help Needed--Elementary Number Theory

    Is it really ALL? That makes this far more interesting. Mind linking a paper or something?
     
  9. Sep 2, 2012 #8
    Re: Professional Help Needed--Elementary Number Theory

    Mandelbra,

    Unfortunately, I have no paper to link to, and by no means is that failing for a lack of searching; but here's a little example of what I mean from the 29th row of the Eulerian Triangle (data courtesy of OEIS). Check any of these values modulo 29 and you'll get the same answer: 1 (mod 29)

    435 1
    436 536870882
    437 68614271237958
    438 286171698369607914
    439 177647455673002199595
    440 31382819428102862274060
    441 2194392886612867977544380
    442 73424846658979203874373100
    443 1323982746583831999659021945
    444 13919693671791536153349072870
    445 90061513941680102366609674650
    446 372321031278485080481062180110
    447 1009202977757986820086345359195
    448 1824120537458837340596389252680
    449 2219711218428375098854998661320
    450 1824120537458837340596389252680
    451 1009202977757986820086345359195
    452 372321031278485080481062180110
    453 90061513941680102366609674650
    454 13919693671791536153349072870
    455 1323982746583831999659021945
    456 73424846658979203874373100
    457 2194392886612867977544380
    458 31382819428102862274060
    459 177647455673002199595
    460 286171698369607914
    461 68614271237958
    462 536870882
    463 1
    https://oeis.org/A173018

    The no-brainer explanation I can't seem to find anywhere almost certainly has to do with the cyclical group nature of the primes...

    - AC
     
    Last edited: Sep 2, 2012
  10. Oct 15, 2012 #9
    Re: Professional Help Needed--Elementary Number Theory

    Quick question: Why would anyone have the desire prove anything after Godel?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Professional Help Needed-Elementary Number Theory
Loading...