- #1
fourier jr
- 764
- 13
my turn to have something answered 
1. Homework Statement
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.
##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)
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)
1. Homework Statement
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.
Homework 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)
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)
