Subscribe via feed.

Maths challenge 4

Posted by Chris on May 12, 2011 – 6:47 pm

Prove that 2^n – 1 does not divide 3^n – 1 where n is any natural number > 1.

Solution: see post 54.


This post is under “MathsChallenge” and has 54 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

54 Responds so far- Add one»

  1. 1. Knightmare Said:

    don’t you mean 3b?

  2. 2. Knightmare Said:

    can’t wait till you get to the 3D question-i’ve got my glasses ready.

  3. 3. Wizard of Oz Said:

    If n is even then let n = 2a, 2^n – 1 = (2^a + 1)(2^a – 1)

    Since 2^a is not divisible by 3 then either 2^a + 1 or 2^a – 1 must be, so 2^n – 1 cannot divide exactly into 3^n – 1.

    If n is odd then let b = n – 1.

    2^n – 1 = 2(2^b – 1) + 1 where b is even.

    2^b – 1 has a factor of 3, so 2^b – 1 = 3m, say

    So 2^n – 1 = 6m + 1, i.e. one more than a multiple of 3

    3^n – 1 is one less or two more than a multiple of 3

    So 2^n – 1 won’t divide into 3^n – 1 whether n is even or odd.

  4. 4. Chris Said:

    LOL. Well observed Knightmare. I’ve changed “Maths challenge 3″ to “Maths challenge 4″.

  5. 5. Chris Said:

    Hi WIz. That’s pretty good. It earns you a cigarillo.

    Two points though – when considering n being odd, it is more straightforward to use e.g. n = 2b + 1 (b = 0,1,2,3,…). Then you get 2^n – 1 = 2^(2b + 1) – 1 = 2*2^(2b) – 1 = 2*4^b – 1 = 2(3+1)^b – 1 = 2 – 1 = 1 (mod 3). i.e. 1 more than a multiple of 3 and of course 3^n – 1 = -1 (mod 3) so is always 1 less (or 2 more if you prefer) than a multiple of 3.

    You had surprised me with 2^even – 1 being a multiple of 3; I had to check it out.

    For n even, I would have set n = 2a (a = 1,2,3,…) to get 2^n – 1 = 2^(2a) – 1 = 4^a – 1 = (3+1)^a – 1 = 1 – 1 = 0 (mod 3).

    Now that Knightmare has mentioned it. I saw I 3D demo yesterday, I felt ill almost immediately – I’m very sensitive to flicker, I can tell a 60Hz CRT monitor straight away. <advert> LG have a polarised plasma screen that let’s you use low cost polaroid specs – and both left and right images are shown at the same time. But I haven’t seen a demo. My dad says it’s excellent. </advert>

  6. 6. slavy Said:

    Don’t rush through it :) I think the problem is pretty tough (I still don’t know the proof and again vaguely recall that I could have dealt with it or something similar as a high school student). Modulo arithmetic works for division arguments ONLY if we have a zero remainder! So I agree that n cannot be even, because then the potential divisor is divisible by 3, making 3 a divisor itself – a contradiction. But I disagree about the odd-n-analysis. Take n=3. Then 3^3-1=26=2*13 and 13=1 (mod 3). So no contradiction here.

    I don’t think I will have time to work on the problem within the next 10 days (working on the thesis + attending conference in USA) so I will leave you on your own :P However, I may check from time to time if the stuff you write is correct or not ;)

  7. 7. Chris Said:

    Am on tube, so typing awkward. I can’t see a fault in Wiz’s solution, especially after my re-analysis.

  8. 8. slavy Said:

    Wiz said that since 2^n-1=6m+1 this is enough to conclude that it is not a divisor, since 3^n-1 does not have divisors of such type. I showed that when n=3 – odd number 3^n-1 is divisible by 13=6*2+1. So this argument fails.

  9. 9. slavy Said:

    Moreover, since 3^n-1 is always even, taking n to be odd
    3^n-1=2*A, where A=6*m+1 :P

  10. 10. Chris Said:

    Hi slavy. I’ve only just got home and have to go out again. Perhaps I skipped over the 6m+1 assertion too quickly. But I think my re-analysis (as I had thought it merely to be) doesn’t have an error.

    I guess you’re suggesting that Wiz should only have won a dogend ;)

    I’ll carefully recheck Wiz’s and your statements, but your last one looking pretty conclusive.

  11. 11. slavy Said:

    Hi Chris. I guarantee that so far there is no correct solution posted to the problem. The mod 3 argument clearly does not work for odd n.

  12. 12. Wizard of Oz Said:

    Slavy, I can’t see what you’re is getting at when n = 3.

    2^n – 1 = 7 and 3^n – 1 = 26. 7 doesn’t divide into 26.

    Are you getting m and n mixed up from my post # 3?

  13. 13. Chris Said:

    Hi slavy. I’m ashamed to say that I’ve only just finally understood your point. Thank you for your persistence. I agree; the proofs that neither expression is divisible by 3 (with odd n) are irrelevant. All we had established was that neither expression was divisible by 3. We need 2^n -1 = 0 (mod m) and 3^n – 1 ≠ 0 (mod m) for some m.

    Wiz is good at suckering me in :( and :) . That’s at least the third time he’s done it over the last few years. Wiz, you win the cigar for that achievement ;)

    So we need a correct argument for the odd n case, or a different argument altogether.

  14. 14. Chris Said:

    Hi Wiz. I missed your post while typing mine. Slavy will not find a failing case for the original assertion because 2^n – 1 does not divide 3^n – 1. But he has found a failing case for (y)our argument.

    All we’ve shown is that for odd n, neither 2^n -1 or 3^n -1 are divisible by 3. Slavy is saying, “so what?”. e.g. 7 divides 35, but neither 7 or 35 are divisible by 3.

  15. 15. w Said:

    Hi Chris, Now I get it. I “suckered” myself as well as you (but not Slavy).

    Back to the drawing board . . .

  16. 16. slavy Said:

    By the way, I am not sure that modulo arithmetic is the tool to attack the problem! Actually, I believe it is not :) Exponential functions are in general difficult to analyze.

    If somebody is still interested in spending their time on the problem I can suggest a different direction (that I will probably explore myself but at least in 10 days). We want to check if (3^n-1)/(2^n-1) is an integer. But there is only one potential candidate for its value. Indeed, (4^n-1)/(2^n-1)-4^n/2^n=1, while the difference (3^n-1)/(2^n-1)-3^n/2^n remains positive, but is obviously smaller than the previous one (i.e., smaller than 1). Thus, in order (3^n-1)/(2^n-1) to be an integer, its value should be exactly [3^n/2^n]+1, i.e., the smallest integer, bigger than 3^n/2^n. So, one can concentrate on estimating this value, instead and compare it with our expression :)

  17. 17. Chris Said:

    Hi slavy. I’d also come to the conclusion that modulo arithmetic wasn’t going to be the (main) tool. I’d started dabbling with a^n – b^n = (a-b)(a^(n-1) + … + b^(n-1)) and (a-b)^n expansions.

  18. 18. Chris Said:

    (3n – 1)/(2n – 1) = 3n(1 – 1/3n)/(2n(1 – 1/2n) =(3/2)n (1- 1/3n)/(1 – 1/2n)
    = (3/2)n (6n – 2n)/(6n – 3n)
    (3/2)n cannot be an integer by the fundamental theorem of arithmetic. To get an integer ratio we need either (6n – 2n)/(6n – 3n) = (2/3)n and that’s clearly impossible, or (6n – 2n)/(6n – 3n) = m (2/3)n, for some integer m, which is also impossible as when n = 2, (6n – 2n)/(6n – 3n) = 1.185… and → 1 as n → ∞

    Aaaargghh. The last bit isn’t quite right. I’ll be back.

  19. 19. Chris Said:

    I’ve decided that was rubbish.

  20. 20. Chris Said:

    Some more progress: n cannot be a multiple of 3. As shown in posts 3 and 5, n cannot be even, so even multiples of 3 automatically won’t do the job (of letting 2n – 1 divide 3n – 1).

    So we only have to consider odd multiples of 3. Let n = 3(2m + 1), m = 0,1,2,3,…

    Then 23(2m+1) -1 = 82m+1 -1 = 1 – 1 = 0 (mod 7)
    But 33(2m+1) -1 = 272m+1 -1 = (-1)2m+1 -1 = -1 -1 = -2 (mod 7).

    Hence n cannot be a multiple of 3.

    I’ve got several ideas running through my bonce, but haven’t put them to paper yet.

  21. 21. Chris Said:

    … unless I’ve gone mad, that means that we are “only” left with n of the form: 6m ± 1, m = 1,2,3,… to consider.

  22. 22. Chris Said:

    Another small chip. n cannot be a multiple of 5.

    25m -1 = 32m -1 = 1 – 1 = 0 (mod 31)
    35m -1 = 243m -1 = 26m -1 = 1 -1 = 0 (mod 31) if and only if m is a multiple of 30 (found by manually checking all m = 1,2,3,…,31). But 30 is both a multiple of 2 and 3 and so fails under mod 3 and 7 inspections respectively.

    So n cannot be a multiple of 2, 3 or 5. Three primes down, phew, only ∞ – 3 to go :)

  23. 23. Chris Said:

    Yet another small chip, n cannot be a multiple of 7.

    27m -1 = 128m -1 = 1 – 1 = 0 (mod 127)
    37m -1 = 2187m -1 = 28m -1 = 1 -1 = 0 (mod 127) if and only if m is a multiple of 18 (found by manually checking all m = 1,2,3,…,128). But 18 is both a multiple of 2 and 3 and so fails under mod 3 and 7 inspections respectively.

    It happens that 127 is prime. Fermat’s little theorem says that for a prime p,
    if gcd(a,p) = 1, then ap-1 = 1 (mod p), , but doesn’t guarantee that there isn’t a smaller power than p-1 that does the job. p-1 = 126 = 2*3²*7 = 18*7, so it’s not especially surprising that 18 pops up.

    So n cannot be a multiple of 2, 3, 5 or 7. Four primes down (only ∞ – 4 to go). That leaves numbers of the form 210m ± 1 to do.

    This will probably be the last post using this technique as I haven’t found a useful way to cover all primes.

  24. 24. slavy Said:

    Hi Chris, I told you – modulo arithmetic is not what will work here. Unfortunately, I still don’t have a clue what should be used instead (still haven’t thought about it deeper, since I don’t want to trap myself and get obsessed – maybe in a month if I successfully submit my thesis)

  25. 25. Chris Said:

    Hi Slavy. I’m now not completely sure that’s right. I posted the last few results as I was moderately happy to have made partial progress – but (finite) number crunching was required :(

    But as often happens, something good come come from failure. I’m chewing over an idea (or two) that if are correct will make me very happy. But they are dependent on the truth of the original assertion of the posed problem. I’ll be posting appropriate comments very soon.

    I wish you the best of luck with your thesis. Will you be doctor slavy then?

  26. 26. slavy Said:

    Hi Chris.. Of course, if the problem is correct, you should be able to kill any single case by one way or the other. The problem is that the cases are infinitely many and we don’t have any general strategy how to do it. This reminds me of an international mathematical olympiad at about a decade ago, when the last problem was “prove that for every prime p…”. One of the Bulgarian competitors solved very quickly the remaining two problems, so he had more than 3 hours for that one. And when you don’t have the picture in your head you usually do case studies until you see a common pattern. He checked the first 50 or so prime numbers (each on a separate sheet!) until the time elapsed and verified that for them the statement holds. The jury was impressed by his enthusiasm so they gave him 2 points out of 7, but this was more then generous. And the actual solution was based (here I am guessing, since I don’t remember) on the distribution of the prime numbers, not on the individual representatives, so he could have been computing paertial cases till death and still wouldn’t have been able to find anything…

    Thank you for the kind wishes regarding the thesis :) Yes, I hope to be a doctor in three months (after you submit, you need to wait at about 6 weeks so that the reviewers read the manuscript and then the actual oral defence takes place).

  27. 27. Chris Said:

    Hi slavy. I wasn’t clear and forthcoming in my “defence” of the use of modulo artithmetic. I only posted the last few cases for fun. I knew that I couldn’t do that forever, hence my “only” ∞ – 3 to go observation. I’m persisting with the modulo approach simply because I really like modulo arithmetic (although I’ve been aware of it for two or three years, it’s still my new toy).

    I’ve noticed that I’ve been unwittingly been using an – 1 is divisible by a – 1. I haven’t yet considered the full ramifications of that fact (with regards to the current problem).

    The (hoped for) happy result (assuming the truth of the posed problem) is that when 3pm = 1 (mod 2p-1), that in 3pm the m always seems to have a prime factor < p. At least, I tentatively conjecture that is the case, but can see that it doesn’t need to be true as the overall failure to divide could for another reason.

    I do intend to publish a table for the next dozen or so primes, even if only to show my conjecture is wrong, LOL. I’m not a professional mathematician, so I can afford to take the risk of making ill-considered (and doomed) conjectures :)

  28. 28. Chris Said:

    As it’s getting late, I’ll only present a vague argument now, with the possibility of making it tighter (and far less vague) later. I believe that the stuff I’ve done in my last few posts is relevant especially my comment post 27 para 3. I shall confine myself to some significant observations and then do a bit of arm waving.

    Let a, m be integers and p be prime and gcd(a,p) = 1, then
    apm -1 = am -1 (mod p). Proof: Fermat’s little theorem => bp-1 = 1 (mod p), when gcd(b,p) = 1. Multiplying by b => bp = b (mod p), in fact then don’t require gcd (b,p) =1. Now simply substitute am for b and subtract 1 from both sides.

    Further (possibly useful), let P and p be prime. Then aPpm – 1 = apm -1 (mod P). This trivially follows from the previous.

    It follows (and I have also shown it by example in recent posts) that 2pm – 1 = 0 (mod 2p -1). I’m thinking P ≥ being 2p -1 might be required.

    It also follows that 2pm -1 = 2p -1 + kp and 3pm -1 = 3p -1 + qp for some integers k and q (both are probably functions of p and m), but I don’t think I need that result or even if it’s useful.

    Arm waving: With am -1 (mod p), the value is unchanged if m is increased by p-1, so there is no need to consider m > p -1. But then m is either a prime or has a prime factor that is less than p. I then assert that we can eliminate each p by induction, using that fact that we know that for p = 2,3,5,7 (as shown in previous posts) that the posted assertion is true. The next p is 11, and so the maximum m to consider is 10. But each value of m in the range m = 1 to p-1 is (in order), 1,2,3,2*2,5,2*3,7,2*2*2,3*3,2*5 and none of those values (or multiples thereof) allow the original division, so 11 doesn’t do it either. Rinse and repeat for all primes. [Later: the 1 is worrying me. I expect that I'll fix that when I get my brain straight].

    Now if only I could write that up properly and get rid of all the vagueness and apply the arguments to the correct equations. Other than that, I believe that I’m on the right track or its verge (after nearly two months). The real excuse for posting such a sloppy mess is to beat Slavy to it (which isn’t fair of me as he has far more important things to do) and to have (sort of) done it using modulo arithmetic methods.

  29. 29. Chris Said:

    Slavy will say the above is pretty well rubbish, and he’d be right. But I’m certain that I’m on the right track. The major howler (which I was aware of) is that I’ve been looking at equations in mod p rather than mod 2p -1. However, I’m pretty confident that m cycles the expression in mod 2p -1 in precisely the same manner as that which I’ve indicated for the mod p equations – that’s the reason that I introduced the identities at the beginning of my last post.

  30. 30. Chris Said:

    Just to illlustrate further what I’m trying to achieve.

    n cannot be a multiple of 11.

    211m -1 = 2048m -1 = 1 – 1 = 0 (mod 2047)
    311m -1 = 967m -1 = 1 -1 = 0 (mod 2047) if and only if m is a multiple of 8 (found by manually checking). But 8 is even and so fails under mod 3 inspection.

    n cannot be a multiple of 13.

    213m -1 = 8192m -1 = 1 – 1 = 0 (mod 8191)
    313m -1 = 5269m -1 = 1 -1 = 0 (mod 8191) if (and only if!) m is a multiple of 70 (found by manually checking). But 70 is even and so fails under mod 3 inspection.

    In this case I note that 8191 is prime and 8190 = 2 * 3² * 5 * 7 * 13 and got lucky by checking with m = 5*7 = 35 (on my third guess) and finding a remainder -1, so doubling m to 70 gives the desired result.

    What I hope to prove is that it will always be the case that m will have a factor that does the job.

    If 2p -1 is not prime, then I’m pretty sure that Euler’s totient idea will also cause a “short-circuit”.

  31. 31. slavy Said:

    Hi, Chris. “we can eliminate each p by induction” – here is the main problem. You can’t :) Induction cannot be applied to such unstructured and chaotic set as the prime numbers are. And I don’t see any (provable) strategy in your computations. Each of them contains the phrase “found by manually checking”, which is exactly the opposite to induction.

    If we are hand-waving, then let me participate :P As I started before (3^n-1)/(2^n-1)=(3/2)^n+(3^n-2^n)/(4^n-2^n), and 3^n<2^n, hence (3^n-1)/(2^n-1) is bigger than (3/2)^n and smaller than (3/2)^n+(3/4)^n. But, at least for small n, there is no integer between (3/2)^n and (3/2)^n+(3/4)^n. I claim this is true in general, and verifying it will solve the problem. Why this is better than the initial problem? We managed to switch from 2^n-1 in the denominator to 2^n, and we know all the dividers of the latter, giving us more help to come up with something…

  32. 32. Chris Said:

    Hi slavy. I’m fully aware that I’m only reformulating the original problem in other terms, and that the reformulation is very likely to be as difficult to prove as the original problem seems to be. However, I’m sure, in view of this post, that you will have some empathy for why I haven’t given up on the modulo arithmetic approach.

    I’ve done some number crunching. The cases when 3pm – 1 = 0 (mod 2p -1) are as follows notation (p,2p-1,m):
    (3,7,2), (5,31,6), (7,127,18), (11,2047,8), (13,8191,70), (17,131071,7710), (19,524287,27594), (23,8388607,7760), (29,536870911,1368). That’s as far as my brother’s rubbish computer can go (Mathematica simply stops running after that). Those (critical) m values are the smallest values that make 3pm – 1 = 0 (mod 2p -1). It is immediately evident that all of the critical m values are even – proving that is always true is equivalent to proving the posed problem (as demonstrated by Wiz way back in comment 3).

    If we multiply that m by any integer, k, then we get 3pmk – 1 = 0 (mod 2p -1). I realise that that is a trivial but essential result.

    Euler’s extension of Fermat’s little theorem is aφ(q) = 1 (mod q). But φ(q) is even for q > 2. Let q = 2p -1. Then it is guaranteed that 3φ(q) -1 = 0 (mod q). Unfortunately, I don’t know how to prove that we can’t divide out all the powers of 2 from φ(q). Proving that would prove the original assertion. I’m aware that e.g. Carmichael’s lambda (a generalisation of Euler’s totient) throws up powers of 2 as being special.

    An aside (for now). I have come across the following extraordinary fact:
    φ(an-1) = 0 (mod n). I haven’t seen a proof but have done a number crunch verification.

    It’s late, so I must stop now.

  33. 33. Chris Said:

    So my previous induction strategy has been greatly simplified (in fact it has been eliminated). I only need to show that m will always be even (LOL). Put another way, I believe it is the case, that if we divide out all the factors of 2 from φ(2p -1) to get φ’ that it will be impossible to find 3φ’ – 1 = 0 (mod 2p -1)

    Of course, I expect that proving that is at least as hard as proving the posed problem.

    Sadly, number crunching this one is too hard for p > 29 – the numbers involved are enormous, 3^(2 billion+) are enormous.

    I think it’s time for me to follows Slavy’s advice, and abandon the modulo arithmetic method.

  34. 34. Chris Said:

    I’ve cracked why φ(an-1) is divisible by n (a, n > 1) (thanks Google).

    Clearly an-1 = 0 (mod an-1) and also clearly, if am-1 = 0 (mod an-1), then m must be a multiple n: m cannot be less than n as (am-1)/(an-1) < 1. In fact an-1 is the smallest positive integer that = 0 (mod an-1): which should be stunningly obvious.

    But Euler says that aφ – 1 = 0 (mod an-1), where φ = φ(an-1), so φ must be a multiple of n. This means that φ(an-1) = kn. A bit of number crunching suggests that k = 1 only when a = n = 2.

  35. 35. Chris Said:

    I have to admit defeat. I have only been able to find a pretty good statistical argument to support the claim. When considering n = p (prime), we get ap-1-1 = 0 (mod p). p-1 is always divisible by 2 (for p >2), but in general, it will have [perhaps many] other [prime] factors and quite often one of the prime factors of p-1, q say, actually satisfies aq-1 = 0 (mod p). We only need one case in the infinite sea of p’s that allows any particular q to be rejected as a candidate.

    For instance (I might be misremembering this, but the gist of my comment is right), it isn’t until we get to p = 127, that we can eliminate q = 5.

    It’s too many days since I did that stuff, but when it was fresh in my mind, it all made sense.

    I have tried several approaches, including trying to find a magic equation like that which slavy was hinting at a while back.

  36. 36. Chris Said:

    AAAARRRRRGGGHHHH. I found a major error in (what was) this post. So I’ve deleted it to save everyone the bother of reading a pile of tripe. Gutted. I’m sorry if I’m too late and you’ve already read it.

  37. 37. slavy Said:

    Hi Chris! I am extremely busy with the finishing of my thesis, so right now I have no time to check your arguments (plus my head is full of a different type of math and I should not mix them). I hope to be able to do so in a couple of weeks, if by then you are still claiming correctness of your solution :)

  38. 38. Chris Said:

    Hi slavy. No problem. As you see, I’ve withdrawn my “proof”. I’d had a brain fart.

  39. 39. Chris Said:

    This is the strongest and simplest argument that I can come up with (so far) is still essentially statistical.

    2n-1 = 0 (mod 2n-1). In particular 2n-1 divides itself once exactly.

    To guarantee that 3m-1 is divisible by 2n-1, Fermat’s little theorem says that we may set m = φ(2n-1). FLT doesn’t guarantee that φ(2n-1) is the smallest number that can do it. φ(2n-1) is guaranteed to be divisible by n.

    But the problem requires that m = n. So we require that we replace φ(2n-1) by n.

    Moreover, there is a function that is considerably better, for this purpose, than Euler’s phi, the Carmichael lambda function. To give some perspective to this, here are a few Carmichael lambda’s for λ’(n) = λ(2n-1) (I’ve skipped the even values of n):
    λ’(3) = 6, λ’(5) = 30, λ’(7) = 126, λ’(9) = 72, λ’(11) = 88, λ’(13) = 8190,
    λ’(15) = 150, λ’(17) = 13170, λ’(19) = 524286, λ’(21) = 1008,
    λ’(23) = 174480, λ’(25) = 1800, λ’(27) = 262656, λ’(29) = 39672.

    λ’(101) = 4183665347287322901039709584
    λ’(201) = 14640502602439406943656275076924064511361346720
    λ’(301) = 1851061211095358505095164611241970436903191003223056652502344473860637071890

    As you see , λ’(n) >> n typically, but we effectively want them to be equal! Idon’t think that’s going to happen.

  40. 40. slavy Said:

    Hi, Chris. It is always hard to give in but maybe it is time for me to wave the white flag, as well :( I still believe that the idea with the lack of an integer between (3/2)^n and (3/2)^n +(3/4)^n is correct, but how to actually prove it is a totally different question. Recently I have been working with binary representations of those numbers and this may lead to something but needs lots of technical work, while I believe there should be something more elegant… So in short words – I would like a hint :P Could you tell me which the source was and maybe this piece of information would give me an incite what the correct approach is?

  41. 41. slavy Said:

    plenty of spelling mistakes above – not in the best shape right now ;)

  42. 42. Chris Said:

    The source simply says “American Mathematical Monthly”. It doesn’t even give a date or any hint about how to do it. The book I found it in was published in 2007.

    It’s been driving me nuts for far too many weeks.

  43. 43. Chris Said:

    Hi slavy. Having given up searching for a solution, I tried a different approach and I have now been successful :) :) :)

    So you can have the pleasure of solving it for yourself, I’ll throw you a bone: consider 2n-1 (mod 12), n odd. That still leaves at least one more inspiration from you.

    If that’s not enough, I’ll give you another if you ask. But I suspect from your posts over the last year+ that might be enough to get you through.

    Gauss would have been able to do prove it.

  44. 44. slavy Said:

    Hi Chris. Thanks for the info. I know approximately the problems difficulty level in the AMM, so I will stay away from high-level calculus. Regarding mod 12 – so far I don’t see anything there. For n-odd, the denominator is congruent 7 mod 12, while the numerator is congruent 2 mod 12. But 7*2=2 mod 12, so it is possible to have 3^n-1=(2^n-1)*(12A+2). I will think a little bit further if I can get a contradiction from here…

  45. 45. Chris Said:

    Hi slavy. Here’s another bone: every prime > 3 is ??? (mod 12) (but I expect you’ll have thought of that before you see this comment). That still leaves a few steps, only one of which requires a more advanced mod arithmetic argument – Gauss would have been the first person who could make that argument without citing a conjecture).

    I’m sorry if I’m being a bit cryptic. I think the last step isn’t obvious. I also assume that you would rather work it out for yourself.

    (No calculus required).

  46. 46. Chris Said:

    Hi slavy. (I’m only considering odd n = 2m-1 where m = 1,2,3,…). I haven’t fully understood all of the official solution yet.

    Although the official solution doesn’t spell it out, I note that every prime > 3 is ±1 or ±5 (mod 12). It follows that any integer not divisible by 2 or 3 must also be ±1 or ±5 (mod 12) and that if the number = 7 = -5 (mod 12), then it have must have at least one prime factor p = ±5 (mod 12).

    If the assertion of non-divisibility is false, then p divides 32m-1-1 => 32m = 3 (mod p). But this would contradict … LOL, I’ll post the rest tomorrow if you haven’t beaten me to it.

  47. 47. Chris Said:

    The extra ingredient mentioned in the solution is the law of quadratic reciprocity. The authors state that 32m = 3 (mod p) contradicts QR. I quote “But this contradicts the quadratic reciprocity theorem (an easy consequence of which is the fact that 3 cannot be a quadratic residue modulo p), since p ≡ ±5 (mod 12)”. (“Easy” – not for me :( ). I cannot see how that does it using the standard formulations of that law.

    However, http://en.wikipedia.org/wiki/Quadratic_reciprocity#.C2.B13 seems to be suggesting that x2 = 3 (mod p) is solvable if p = ±1 (mod 12) but not solvable if p = ±5 (mod 12), but it doesn’t seem to be completely as clear cut as that.

    The source book is “The Maths Problems Notebook” by Valentin Bojou and Louis Funar. The problem is numbered 1.27.

    I shall spend as much time as necessary to “fully” understand QR. I think it (and the whole modulo arithmetic thing) are fascinating. I’m further driven by noting that Gauss calls the law of QR the “golden theorem” and that he regarded it as his favourite theorem from number theory.

  48. 48. slavy Said:

    Thanks, Chris :) I have completely forgotten this theorem (shame on me :( ) and its powerful corollaries, so I admit I would have had no chance to solve the problem that way.

  49. 49. Chris Said:

    Hi slavy. I had an idea that although you were familiar with a(p-1)/2) = ±1 (mod p), that you weren’t up to speed on QR (any more).

    But I do remain rather baffled by all the apparent supplements to QR.

  50. 50. Chris Said:

    Hi slavy. I can’t see how to use QR directly to see the case for a residue of 3. Is it possible to do that, or do you really need all those (presumably infinitely many) supplementary rules?

  51. 51. Chris Said:

    Hi slavy (and anyone else who might be interested) here’s the missing details. To follow this completely, you’ll need to do some homework. But here’s a brief summary of quadratic reciprocity.

    Define the Legendre symbol, (a/p) = (a(p-1)/2 mod p), where p is prime and gcd(a,p) = 1. From Fermat’s little theorem (FLT), we have ap-1 = 1 (mod p). It follows that (a/p) = ±1. Proof outline: If r2 = 1 (mod p), then (r-1)(r+1) = 0 (mod p). (r-1) and (r+1) must be factors of p, but p is prime, so one factor must be 1 and the other 0. So r = ±1. QED.

    Consider the equation: x2 = a (mod p). If it is possible to solve that for x (for a given a and p), then a is said to be a quadratic residue (mod p), otherwise it is a quadratic non-residue. Theorem (Euler’s criterion): the equation can be solved IFF (if and only if) (a/p) = 1. I shan’t prove that, but I’ll indicate it’s relevance: x2 = a (mod p), raisng to the power (p-1)/2 => a(p-1)/2 = xp-1 = 1 (mod p), the last bit follows from FLT. (Technical point: if a = 0 (mod p), then the equation is trivially solved with x = 0 (mod p). If a ≠ 0, then x cannot = 0 (mod p) and so gcd(x,p) = 1, so the conditions of FLT are satisfied).

    QR. It is obvious that (1/p) = 1. Supplement 1: (-1/p) = (p mod 4).
    Proof: (-1/p) = ( (-1)(p-1)/2 mod p). If (p-1)/2 = 2k, then p = 4k+1 => (-1/p) = 1. If (p-1)/2 = 2k -1, then p = 4k-1, => (-1/p) = -1. NB I’m using (p mod 4) rather than p (mod 4), to show the mod is local. i.e. (-1/p) really is ±1, it is not merely congruent to 1 (mod p).

    I shan’t be using it, but, Supplement 2 (Gauss): (2/p) = (-1)(p^2 -1)/8 and that = 1 if p = ±1 (mod 8 ) and -1 if p = ±3 (mod 8 ) . The proof of that isn’t obvious (but it is straightforward, see: http://www.proofwiki.org/wiki/Second_Supplement_to_the_Law_of_Quadratic_Reciprocity ).

    QR: (p/q)(q/p) = (-1)(p-1)(q-1)/4, where p and q are odd primes. NB this was first proven by Gauss. He wrote 8 different proofs altogether, and there are over 200 proofs so far. I’m not surprised – the theorem is quite extraordinary. It is customary to note that if (q/p)(p/q) = 1, then, either both p and q are mutually quadratic residues or quadratic non-residues. If (q/p)(p/q) = -1, then, mutually, one (of q or p) is a quadratic residue and the other is a quadratic non-residue.

    By the definitiion of the Legendre symbol, (a/p)(b/p) = (ab/p), and it follows that (a2/p) = (a/p)(a/p) = (a/p)2 = 1. [Later: if (q/p)(p/q) = k, then (q/p) = k(p/q)]

    Back to the problem. We got to 32m = 3 (mod p) where p is a prime of the form 12k ±5 (NB -5 = 7 (mod 12)), and we need to show that that is impossible. The fact that 3 appears on the LHS is irrelevant. I’m actually going to show that x2 = 3 (mod p) IFF p is a prime of the form 12k ±1 as that is more useful.

    (3/p)(p/3) = (-1)(p-1)(3-1)/4 = (-1)(p-1)/2 = (-1/p) = (p mod 4).
    Also (p/3)= p(3-1)/2 = (p mod 3)

    (3/p)(p/3) = (-1/p). Multiply both sides by (p/3) and using (a/p)(a/p) = 1 => (3/p) = (-1/p)(p/3) = (p mod 4)(p mod 3). Now, every prime > 3 is of the form 12k + r, where r = ±1 or ±5 (or r = 1,5,7 or 11 if you prefer). (I’ll leave that as homework). NB as a bonus we see that (3/p) = (-p/3)
    (p mod 12) (p mod 3) (p mod 4) (3/p)
          1                1              1           1
          5               -1              1          -1
          7                1             -1          -1
        11               -1             -1           1
    So (3/p) = 1 IFF p = ±1 (mod 12).

  52. 52. Chris Said:

    I’m just playing with my new toy. I note that if a is the QR of interest, then from (a/p)(p/a) =(-1)(a-1)(p-1)/4 we immediately deduce that (a/p) = (p/a)(-1)(a-1)(p-1)/4.

    I thought I’d have a bash with a = 5. (p/5) = (p(5-1)/2 mod 5) = >
    (p/5) = (p2 mod 5). Also (-1)(a-1)(p-1)/4 => (-1)(5-1)(p-1)/4 = (-1)p-1.
    For odd primes p, (p-1) = 2k, so (-1)p-1 = 1, nice. Therefore (5/p) = (p2 mod 5). So we need to solve p2 = 1 (mod 5). That’s easy: All primes > 5 are of the form 10k ±1 or 10k ±3. If p is of the form 10k ±3, then p2 = 100k2 ±60k +9 = -1 (mod 5), so they don’t work. If p is of the form 10k ±1, then p2 = 100k2 ±20k +1 = 1 (mod 5). So complying primes must be of the form 10k ±1, and that’s my final answer.

  53. 53. Chris Said:

    Last go with this topic. I can’t find a proper confirmation of the following result that for a QR of 7 we need p = ±1,±3,±9 (mod 28).

    (7/p) = (p/7) (-1)(p-1)(7-1)/4 = (p/7) (-1)(p-1)/2
    (I used (-1)3 = -1). As before, (-1)(p-1)/2 = (p mod 4).
    (p/7) = p3 (mod 7) = ±1, for our purposes. Because we have mod 4 and mod 7 to consider, it is most natural to use the following: any number n = 28k + r, where r = 0,1,2,…,27. But we want n to be a prime p, so that leaves us with r = 1,3,5,9,11,13,15,17,19,23,25,27. So now make a table of r3 mod 7 and (r mod 4) and calculate the products.

    r           1   3   5   9  11  13  15  17  19  23  25  27
    r3 mod 7    1  -1  -1   1   1  -1   1  -1  -1   1   1  -1
    r  mod 4    1  -1   1   1  -1   1  -1   1  -1  -1   1  -1
    (7/p)       1   1  -1   1  -1  -1  -1  -1   1  -1   1   1
    

    So p = 28k + 1,3,9,19,25,27 = 28k ±1,±3,±9

  54. 54. Chris Said:

    SOLUTION: I’ve collected the relevant stuff here as the solution is scattered over too many posts and is difficult to follow.

    The principle is to show that 2n-1 and 3n-1 cannot have a common prime factor.

    2n-1 = -1 (mod 2) and so cannot have a factor of 2.
    3n-1 = -1 (mod 3) and so cannot have a factor of 3.
    So any common prime factors of both must be ≥ 5.
    Also, if n = 2m is even, then 22m-1 = 4m-1 = 1-1 = 0 (mod 3). So n must be ≥ 3 and odd if the division is possible.

    If p is a common prime factor of 2n-1 and 3n-1, then p also divides 3(3n-1). We know n must be odd, so let n = 2m-1. Then we have 3(32m-1-1) = 0 (mod p) => 32m = 3 (mod p). Substituting x for 3m => x2 = 3 (mod p). I have shown in the last part of post 51, that according to the law of quadratic reciprocity, that is only possible if p is of the form 12k ±1.

    All primes ≥ 5 must be of the form 12k ±1 or 12k ±5. Proof: Any number may be written as 12k ±r, where r=0,1,2,3,4,5,6. For primes ≥ 5, we may remove all the remainders that are a multiple of 2 or 3 => p = 12k ±1 or 12k ±5.
    The product of two numbers of the same form is a number of the form 12k ±1.
    The product of two numbers of different forms is a number of the form 12k ±5.

    If n ≥ 3 is odd, then 2n-1 = 7 = -5 (mod 12). Proof: If n = 3, we get 8-1 = 7 = -5. Add 2 to n => 23+2-1 = 8*4 -1 = 7. Each time we add 2 to n, we simply multiply the previous 8 by 4 to get 8 (mod 12) again. So, it must be that 2n-1 has a prime factor, p, of the form 12k ±5 and so cannot divide 3n-1. That concludes the proof.

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0