1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Floor of ratio of Fermat numbers

  1. Apr 1, 2015 #1
    my turn to have something answered o0)

    1. The problem statement, all variables and given/known data

    The problem is to show that Fermat numbers are relatively prime, which I could just look up somewhere but I want to use the mod operator that is used in Concrete Math, which says ##n \bmod m = n - m\lfloor{\frac{n}{m}}\rfloor## So if m<n the problem is to find

    $$(2^{2^n} + 1)\bmod(2^{2^m} + 1) = (2^{2^n} + 1) - (2^{2^m} + 1)\Big\lfloor{\frac{2^{2^n} + 1}{2^{2^m} + 1}}\Big\rfloor$$

    which the book says is 2. It's the part about simplifying the floor part that I'm hung up on.

    2. Relevant equations
    ##n \bmod m = n - m\lfloor{\frac{n}{m}}\rfloor##

    fractional part of x: ##\{x\} = x - \lfloor x \rfloor##

    ##\lfloor x+y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor## or ##\lfloor x \rfloor + \lfloor y \rfloor + 1## depending on the size of ##\lfloor \{x\} + \{y\} \rfloor##

    ##\lfloor x + n \rfloor = \lfloor x \rfloor + n## (n an integer)

    3. The attempt at a solution
    I have a feeling I'm just missing something obvious about exponents or floors. Maybe it's the exponent in the exponent that's throwing me off. Anyway a couple things I've tried:

    $$\Big\lfloor \frac{2^{2^n}}{2^{2^m}+1} + \frac{1}{2^{2^m}+1} \Big\rfloor = \Big\lfloor \frac{2^{2^n}}{2^{2^m}+1} \Big\rfloor + \Big\lfloor \frac{1}{2^{2^m}+1} \Big\rfloor + \Big\lfloor \Big\{ \frac{2^{2^n}}{2^{2^m}+1} \Big\} + \Big\{ \frac{1}{2^{2^m}+1}\Big\}\Big\rfloor$$

    $$\Big\lfloor \frac{2^{2^n}+1}{2^{2^m}+1}\Big\rfloor = \Big\lfloor \frac{2^{2^n - 2^m}+ 2^{-2^m}}{1 + 2^{-2^m}} \Big\rfloor$$ (thinking that the denominator on the right-hand side would be close enough to 1 that it would simplify easily)
  2. jcsd
  3. Apr 1, 2015 #2
    I do not get this, Fy = 2 * prod(k=0 to y, Fk), where Fk = 2^(2^k))-1 ,
    so Fy is relatively prime to all Fermat numbers less than it. qed
  4. Apr 2, 2015 #3
    What about the question I actually asked, about the floor, etc? I know I could look up another proof of that just about anywhere but it seems not this one. I doubt it's even very hard since it's in the 'basics' section of the problems in this chapter.
  5. Apr 2, 2015 #4


    User Avatar
    Science Advisor
    Homework Helper

    Just because it's in the 'basics' section doesn't mean that every method of approaching the problem is equally tractable. I have no idea how you would approach simplifying that floor function. I don't think this problem even belongs in the 'basics' section unless the text has already given you some hints about properties of the Fermat numbers. They must have said some stuff beyond the basic definition.
  6. Apr 3, 2015 #5
    OK, my error.
    The correct equation is (Concrete Mathematics, page 501):
    fn = 2 + f0*f1*...*fm*...*f(n-1) = 2 + k * fm
    so that fn % fm = 2.

    This is in fact the simple way to prove the fractional expression is 2.
  7. Apr 3, 2015 #6
    ...yeah a lot simpler. I even saw that identity in the answers but didn't make the connection. I thought I was just missing something simple about floors or exponents but I wasn't even right about that but I see it now... :confused:
  8. Apr 4, 2015 #7
    You probably figured out to show f0*f1*...*fn = 2^2^n - 1 by expressing the terms in binary.
    So f0 = 3 = 11 binary, f1 = 101 binary, f0*f1 = 1100 + 11 = 1111 binary = 2^2^2 - 1,
    f0*f1*f2 = 1111 * 10001 = 11110000 + 1111 = 11111111 bin = 2^2^3 - 1,
    It's pretty how there are just enough zeros to avoid carries.
  9. Apr 4, 2015 #8
    I didn't try the arithmetic but I remember reading in the text that the reason a lot of a biggest prime numbers known are Fermat primes is that they have the form (1111....11)2 which makes it easier for a computer to work with, or that it avoids unnecessary calculations converting it to base 10.
  10. Apr 4, 2015 #9
    I meant Mersenne primes. I was wrong about that too. :rolleyes:
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted