Questions tagged [fermat-numbers]
In mathematics, a Fermat number, named after Pierre de Fermat who first studied them, is an integer of the form $$F_{n} = 2^{2^n} + 1$$ where $n$ is a nonnegative integer. The first few Fermat numbers are: $$3,\ 5,\ 17,\ 257,\ 65537,\ \cdots $$
128
questions
2
votes
0
answers
56
views
Help me correct my thinking of Fermat's last theorem
Fermat's last theorem as per the wiki states that
No three positive integers a, b, and c satisfy the equation $a^n + b^n = c^n$ for any integer value of $n>2$.
I just recently came across the ...
- 29
3
votes
0
answers
81
views
Is the "reverse" of the $33$ rd Fermat number composite?
If we write down the digits of the $33$ rd Fermat number $$F_{33}=2^{2^{33}}+1$$ in base $10$ in reverse order , the resulting number should , considering its magnitude , be composite.
But can we ...
- 83.2k
2
votes
0
answers
203
views
Smallest prime factor of this $40$ million digit number?
Concatenate the Fermat numbers $F_0=2^{2^0}+1$ to $F_{26}=2^{2^{26}}+1$ in base $10$.
This gives $$3517257655374294967297\cdots9215379822913519617$$ a huge number with $$40\ 403\ 579$$ digits. Because ...
- 83.2k
2
votes
0
answers
39
views
Can you prove that my candidate PRP test for Wagstaff numbers (based on Elliptic Curve Primality Proving for Fermat numbers) is a true Primality Test?
The test is explained and described in the forum of the GIMPS project:
https://www.mersenneforum.org/showthread.php?t=28658
In short:
$$x_1=W_3=3 \ , \ x_{j+1} = \frac{x_j^4+2x_j^2+1}{4(x_j^3-x_j)}$$...
- 373
-1
votes
1
answer
202
views
for what all n is $2^n≡ 3\pmod{ 13}$ true. Please find below my initial steps [duplicate]
$a_n=(2^n)−3 $
, how do we find which $a_n$ are divisible by 13? Or we can re write it as
for what all n is $2^n≡ 3\pmod{13}$ true.
$16≡ 3mod 13$ or $2^4≡ 3\pmod{13}$
$2^{4n}≡ 3^{n}\pmod{13}$ or
$2^{...
- 11
-1
votes
1
answer
52
views
Fermat's Figurate Number Theory [closed]
$$\sum_{i=1}^n \frac{i(i+1)...(i+k-1)}{k!}=\frac{n(n+1)...(n+k)}{(k+1)!}$$
Regard "k" as a fixed positive integer,
How can I prove this formula of Fermat by using induction on "n". ...
- 21
3
votes
0
answers
60
views
Is it possible that only finitely many Fermat numbers are composite?
The current status of the Fermat numbers $$F_n=2^{2^n}+1$$ where $n$ is a nonnegative integer , is that it is prime for $n\le 4$ and composite for $5\le n\le 32$
It is conjectured that only finitely ...
- 83.2k
0
votes
0
answers
32
views
Quadratic residues and their using in proving the Édouard Lucas theorem related to Fermat numbers. [duplicate]
I was doing a study on Fermat Numbers when I came across this theorem by Édouard Lucas (unproven in my reference material):
Every prime divisor of $F_n = 2^{2^{n}} + 1$ is of the form $k \cdot{2^{n+2}...
- 148
1
vote
0
answers
71
views
Why can't I fit certain numbers back into the formula from Fermat's little theorem?
I'm given that the formula for Fermat's little theorem:
$$ a^{-1} \equiv a^{p-2} \ (mod \ p) $$
I presume I would then be able to get an inverse mod directly from this formula. Let's say $p=7$ and $a=...
- 3,428
0
votes
0
answers
61
views
Proving that each Fermat number is prime iff $F_n | 3^{\frac{F_n-1}{2}}+1$.
I am getting into a bit of number theory and came up with the following exercise:
Exercise. Show that each Fermat number is prime iff $F_n | 3^{\frac{F_n-1}{2}}+1$.
My only idea follows (it is not a ...
- 1,722
0
votes
1
answer
42
views
Is this proof, about Fermat numbers being coprime, wrong?
Let $m, n$ be positive integers, with $m > n$ and $2^{2^m}+1$ and $2^{2^n}+1$, Fermat numbers.
To prove that both Fermat numbers are coprime, it's sufficient to state $$\begin{align}(2^{2^m}+1, 2^{...
- 51
0
votes
1
answer
50
views
Help identify this prime number theorem [duplicate]
Studying thoroughly a physics matrix system I found (I'm pretty sure that I'm not committing errors) that for $P$ prime number and $n$ any integer $n<P$, we can decompose,
$$\binom{P}{n}=P \ q$$
...
- 159
2
votes
1
answer
102
views
Find solution using infinite descent.
Can someone help with a task? Need to find a solution other than $(0,0,0) $ with infinite descent. $x,y,z\in\mathbb{Z}$. Any help would be appreciated.
The equation is $x^2-3y^2=2z^2$.
I tried to ...
- 33
1
vote
1
answer
65
views
proof that $(b^n-1)/(b-1)$ is not prime if n is a pseudoprime not prime of the base $b$.
The question of my exercise says:
Proof that, if $n$ is a pseudoprime not prime of the base $b$
(i.e. $b^{n-1}\equiv 1 (\mod n)$)
then
$N=(b^n-1)/(b-1)$ is also a pseudoprime not prime.
I have proven ...
- 33
0
votes
1
answer
64
views
Tweaking Fermat's primality test - Why does it work and should I expect different results?
Fermat's primality test states that for any $p$ as a positive odd integer, IF:
$$a^{{p-1}}\equiv 1{\pmod {p}}$$
or in a different way:
$$a^{{p}}-a\equiv 0{\pmod {p}}$$
THEN $p$ is probably prime.
...
- 1,395
1
vote
1
answer
75
views
Prove that a squared number is an equivalence relation of $-1\pmod{p}$ [duplicate]
Prove that a squared number is an equivalence relation of $-1\pmod{p}$.
Lets assume that $p$ is a prime number which satisfies:
$$p \,\equiv\, 1 \pmod{4}.$$
How can one find a natural number $n$, ...
- 33
-1
votes
2
answers
237
views
Is $3$ the only prime that is both a Mersenne prime and a Fermat prime?
A Mersenne prime is a prime of the form $2^n-1$. A Fermat prime is a prime of the form $2^n+1$. Despite the two being superficially very similar, it is conjectured that there are infinitely many ...
4
votes
2
answers
163
views
Prove that no Fermat number is a $3$ rd power of an integer.
Let $F_n$ be the $n$ th Fermat number, $F_n:=2^{2^n}+1$.
I have been working with a similar question that reads: "Prove that no Fermat number is a perfect square." Where I found an answer ...
- 41
1
vote
2
answers
107
views
Can the substitution be different in this proof of a Fermat theorem?
I was reading one of the Fermat theorem proof from the wikipedia
Specifically the theorem: " If $2^{k}+1$ is an odd prime, then $k$ is a power of 2."
In the proof it says:
Substituting $a=2^...
- 1,579
0
votes
0
answers
49
views
Showing that if $m \leq 2^n-1$, then the $m$-th Fermat number divides $2^{F_n}-2$ [duplicate]
The $m$-th Fermat number is defined by $F_m = 2^{2^m}+1$ (where $m\geq 0$ is an integer).
The condition that we must show is equivalent to $2^{F_n} = 2^{2^{2^n}+1} \equiv 2$ modulo $F_m$. This also ...
- 183
1
vote
2
answers
119
views
Fermat number proof
I want to show that $F_n≡ 2 (mod F_i)$ for $i < n$, where $F_n$ is a Fermat number. My thoughts so far:
$2^{2^n}+1≡0 (mod F_n)$, so it follows that $2^{2^n}≡-1(modF_n)$. Squaring and then adding ...
- 155
0
votes
0
answers
343
views
In regards to the Beal's conjecture
Studying the Beal's conjecture, it states: $A^x + B^y = C^z$, where $A, B, C, x, y$ and $z$ are positive integers and $x, y$ and $z$ are all greater than $2$, then $A, B$ and $C$ must have a common ...
- 1,395
-6
votes
1
answer
86
views
modular arthmetic
To prove that a number p is prime we use this formula $a^{p-1} \pmod p = 1$
In the case of high powers can we derive a formula to solve higher power orders:
$a^{p-1} \pmod p = 1$
$(a^{p-2}) (p-1) \...
0
votes
1
answer
585
views
Showing that $p$ is a Fermat prime if and only if every quadratic non-residue mod $p$ is also a primitive root mod $p$ [duplicate]
I want to show that $p$ is a Fermat prime $\iff$ every quadratic non-residue of $p$ is also a primitive root mod $p$
These are some facts that I know:
$F_n = 2^{2^n} + 1$
Every prime divisor $p$ of $...
- 580
2
votes
1
answer
93
views
Number Theory: Prove for all $1\leq n \in \mathbb{N}$ $F_n \mid 2^{F_n}-2$ with $F_n$ is Fermat numbers [duplicate]
Number Theory: Prove for all $1\leq n \in \mathbb{N}$ $F_n \mid 2^{F_n}-2$ with $F_n$ is Fermat numbers
Follow the following sections They will guide you in proof
Use polynomial division to prove ...
- 748
-4
votes
0
answers
45
views
Fermat numbers question. [duplicate]
The question is to prove, by long polynomial division, that:
$(2^{2^{(n+1)}}−1) | 2^{(Fn - 1)}−1$
$Fn = 2^{2^n}+1$
- 1
0
votes
2
answers
100
views
Fermat numbers question
I am looking for direction in my question.
The question is to prove, by long polynomial division, that:
\begin{equation}
2^{2^{n+1}}-1\ |\ 2^{F_n-1}-1
\end{equation}
I have tried a lot of things, ...
- 85
2
votes
2
answers
79
views
Prove the identity $\frac{1}{1+x^{1}}+\cdots+\frac{2^{n}}{1+x^{2^{n}}}=\frac{1}{x-1}+\frac{2^{n+1}}{1+x^{2^{n+1}}}$
Show that for all non-negatives integers $n$, it is true that
$$\frac{1}{1+x^{1}}+\frac{2}{1+x^{2}}+\frac{4}{1+x^{4}}+\frac{8}{1+x^{8}}+\cdots+\frac{2^{n}}{1+x^{2^{n}}}=\frac{1}{x-1}+\frac{2^{n+1}}{1+...
- 161
1
vote
4
answers
517
views
Stuck on middle step of proof that $a^{p(p-1)}=1 \pmod{p^2}$
I have a question on my homework that says to prove $a^{p(p-1)}\equiv 1 \pmod{p^2}$ and hints at using the proof for fermats little theorem as something to get us started. A TA also hinted at using ...
- 131
2
votes
1
answer
199
views
If p is a prime divisor of the n-th Fermat number, and k is the multiplicative order of 2 mod p then $k|p-1$
In the question Multiplicative order with Fermat numbers, it is established that if p is a prime divisor of the n-th Fermat number $F_n=2^{2^n}+1$ then the multiplicative order of 2 mod p is $k=2^{n+1}...
- 426
2
votes
1
answer
214
views
Fermat's little theorem, Poulet numbers, Carmichael numbers, and primes
Fermat's primality test for base 2 permits Poulet numbers to pass the test, as follows: $(2^x - 2)/x$. Fermat's primality test in different bases will act as a sieve for eliminating most pseudo ...
- 21
4
votes
1
answer
117
views
Prove that $\gcd(2^{2^{22}}+1,2^{2^{222}}+1)=1$
The great common divisor (gcd) of $2^{2^{22}}+1$ and $2^{{2}^{222}}+1$ is
My work,
\begin{align}
F_{n}-2&= 2^{2^{n}}+1-2 \\
&=(2^{2^{n-1}}+1)(2^{2^{n-2}}+1)(2^{2^{n-2}}-1)\\
&=(2^{2^{m}}+1)...
user801681
1
vote
0
answers
128
views
The greatest prime factor of $2^n+1$
Let $f(n)$ be the greatest prime factor of $2^n+1$
Is it true that for any $c>0$ ,there is an integer $n>c$ such that $f(n+1)<f(n)$ ?
This is true if there are infinitely many Fermat primes:...
- 15.8k
-1
votes
1
answer
108
views
Fermat numbers, GCD and proving existence of infinite primes [closed]
Prove that if a, m, n are positive integers with $m ≠ n$, then
$gcd({a^2}^n+1,{a^2}^m+1)=1$ if $a$ is even and $2$ if a is odd.
Use this to show that there are infinitely many primes.
WHAT?! i do not ...
- 613
1
vote
1
answer
351
views
Show that $2^{(p-1)/2} \equiv 1\: \mathrm{mod}\:p$? [duplicate]
Let $F_n = 2^{2^n}+1$ be the $n$th Fermat number for $n \geq 2$ and $p$ a prime factor of $F_n$.
How can I show that that $2^{(p-1)/2} \equiv 1 \:\mathrm{mod}\:p$?
3
votes
1
answer
160
views
$F_n$ is the $n$-th Fermat Number. Prove there are infinitely many values of n for which $F_n + 2$ is composite.
$F_n$ is the $n$-th Fermat Number. $F_n = 2^{2^n} + 1$. Prove there are infinitely many values of n for which $F_n + 2$ is composite. I tried using reduce modulo 7 but got stuck. Any help is ...
- 293
1
vote
0
answers
79
views
The constuctability of n-gon(regular n-polygon)
The problem is as follows.
Let $p$ is odd prime and suppose that a regular $p$-gon is constructible. Then show that $p$ is a Fermat prime.
I solved the $$\Bigg[\Bbb Q\left(\cos\frac{2\pi}{p}\right)...
- 27
10
votes
1
answer
334
views
Can a composite number $3\cdot 2^n + 1$ divide a Fermat number $2^{2^m}+1$?
In OEIS entry A204620, there is a question (by Arkadiusz Wesolowski) about whether composite numbers of the form: $$3\cdot 2^n + 1$$ can be divisors of a Fermat number, i.e. of a number of the form $2^...
- 5,107
2
votes
0
answers
75
views
Odd perfect numbers having as prime factors exclusively Mersenne primes and Fermat primes: reference request or proposal as an exercise
I don't know if the following question is in the literature, please add a commment if it is in the literature (I add my thoughts and motivation below in last paragraph, it is discursive and ...
2
votes
1
answer
231
views
On characterizations for near-square primes and Fermat primes in terms of equations involving arithmetic functions
In this post we denote the Euler's totient function that counts the number of positive integers $1\leq k\leq n$ such that $\gcd(k,n)=1$ as $\varphi(n)$, and the sum of divisors function $\sum_{1\leq d\...
2
votes
1
answer
133
views
Prime numbers of the form $\,1+(p-1)^n$, with $\,p\,$ prime
Given a prime number $\,p\gt2\,$ and a positive integer $\,n\gt1$, let's define the function
$$f_n(p)=1+(p-1)^n$$
Of course, if $\,n\,$ is odd the function is divisible by $\,p\,$, while if $\,n\,$ is ...
- 1,828
2
votes
0
answers
74
views
Natural numbers $n$, $k$ are given such that for any prime $p$ there exists an integer $a$ satisfying the condition $p\mid a^k-n$.
Natural numbers $n$, $k$ are given such that for any prime $p$ there exists an integer $a$ satisfying the condition $p\mid a^k-n$. Decide whether $n$ must necessarily be the $k$-th power of a natural ...
- 291
1
vote
0
answers
79
views
About the probability that the number of Fermat primes is infinite. [duplicate]
I am asking about the probability that the number of Fermat primes is infinite. There is a lot of things similar to the case of Mersenne primes. But it was conjectured that the number of Mersenne ...
- 3,776
3
votes
1
answer
95
views
A proof about period length
In this page: http://mathworld.wolfram.com/FermatPrime.html
I found the following result:
$2^{2^{k}}+1$ is a Fermat prime if and only if the period length of $1/(2^{2^{k}}+1)$ is $2^{2^{k}}$.
I am ...
- 3,776
0
votes
1
answer
205
views
Overflow when performing convolution using Number theoretic transforms (NTT)
I would like to implement fast algorithm for multiplication (SSA algorithm) of arbitrarily long integers with a number theoretic transform (e.g. Fermat number transform). But as number of elements (...
2
votes
1
answer
60
views
Can we deduce that there is infinitely many indices $n$ such that the period length of $1/(2^{2^n}+1)$ is strictly less then $2^{2^n}$.
In this page (http://mathworld.wolfram.com/FermatPrime.html) we have the following result:
$2^{2^n}+1$ is a Fermat prime if and only if the period length of $1/(2^{2^n}+1)$ is equal to $2^{2^n}$. In ...
- 3,776
2
votes
1
answer
141
views
Find all integer solutions to $p^n+n=(n+1)^k$ where p is a prime of the form $2^m+1$
Find all integer solutions to :
$$p^n+n=(n+1)^k,$$
where $p$ is a prime of the form $2^m+1$.
I tried using binomial expansion and substituting $n$ with $c\times 2^m$ where c is a real number......
- 23
0
votes
2
answers
505
views
How can I find the inverse of number using Fermat's Little Theorem or Euler's Theorem? [closed]
Specifically the inverse of 101 and with n = 31200.
$101^{-1} \mod 31200 $
- 3
1
vote
2
answers
97
views
Showing that the Fermat number $F_j$ divides $F_k - 2$, where $0 \le j \lt k$
I have been instructed to solve this problem, at least in part, by showing that $F_k\equiv 2\pmod {F_j}$.
I started out thus (edited to include tentative solution):
$$2^{2^j}+1\equiv 0\pmod {F_j}$$
$...
- 117
2
votes
0
answers
224
views
How to describe the primes not dividing any Fermat number?
It was only last week that I noticed the awesome proof for the infinity of primes, inferred by the Fermat numbers $F_m=2^{2^m} +1,\,m=0,1,2,3,\ldots\:$ being pairwise coprime$-$a book proof indeed!
...
- 6,134