# Floor of ratio of Fermat numbers

1. Apr 1, 2015

### fourier jr

my turn to have something answered

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. Apr 1, 2015

### Zerodivisor

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

3. Apr 2, 2015

### fourier jr

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.

4. Apr 2, 2015

### Dick

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.

5. Apr 3, 2015

### Zerodivisor

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.

6. Apr 3, 2015

### fourier jr

...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...

7. Apr 4, 2015

### Zerodivisor

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.

8. Apr 4, 2015

### fourier jr

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.

9. Apr 4, 2015

### fourier jr

I meant Mersenne primes. I was wrong about that too.