Skip to main content

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
36 views

Why does the Carlyle circle method fail to produce a regular n-gon for non-prime Fermat numbers?

The Carlyle circle method readily produces a regular pentagon, 17-gon, 257-gon and it seems the 65537-gon DeTemple, Duane W. (Feb 1991). "Carlyle circles and Lemoine simplicity of polygon ...
ELA's user avatar
  • 11
2 votes
0 answers
61 views

Conjecture about Proving Primality of Fermat numbers by Elliptic Curves technic

In 2008 and 2009, Denomme-Savin and Tsumura provided 2 papers providing a Primality Test for Fermat numbers based on Elliptic Curves technic: $$ \text{Let } DST(x)= \frac{\displaystyle x^4+2x^2+1}{\...
Tony Reix's user avatar
  • 393
1 vote
1 answer
110 views

Smallest prime of the form $\frac{a^n + 1}{a+1}$ has $ 1 < n < a + 2$?

Consider primes of the form $$\frac{a^n + 1}{a+1}$$ for integer $a>1$ and integer $n>1$. Conjecture : (for any fixed $a$) The smallest prime of the form $\frac{a^n + 1}{a+1}$ has $ 1 < n < ...
mick's user avatar
  • 16.4k
2 votes
0 answers
58 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 ...
paganpasta's user avatar
4 votes
1 answer
178 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 ...
Peter's user avatar
  • 85.1k
2 votes
0 answers
216 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 ...
Peter's user avatar
  • 85.1k
2 votes
0 answers
50 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)}$$...
Tony Reix's user avatar
  • 393
-1 votes
1 answer
244 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^{...
Abhi's user avatar
  • 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". ...
Deniz Belevi's user avatar
3 votes
0 answers
88 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 ...
Peter's user avatar
  • 85.1k
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}...
Nick Larry's user avatar
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=...
xenon's user avatar
  • 3,438
0 votes
0 answers
86 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 ...
xyz's user avatar
  • 1,141
0 votes
1 answer
48 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^{...
agus's user avatar
  • 51
0 votes
1 answer
54 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$$ ...
Euler's user avatar
  • 159
2 votes
1 answer
110 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 ...
Katli's user avatar
  • 33
1 vote
1 answer
82 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 ...
Boncom's user avatar
  • 33
0 votes
1 answer
67 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. ...
Isaac Brenig's user avatar
  • 1,405
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$, ...
Prime_Number's user avatar
-1 votes
2 answers
254 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 ...
Jose Arnaldo Bebita Dris's user avatar
4 votes
2 answers
204 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 ...
joefro's user avatar
  • 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^...
Jim's user avatar
  • 1,609
0 votes
0 answers
51 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 ...
ANT Learner's user avatar
1 vote
2 answers
127 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 ...
user604270's user avatar
0 votes
0 answers
393 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 ...
Isaac Brenig's user avatar
  • 1,405
-6 votes
1 answer
87 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) \...
Abdelrahman Swelam's user avatar
0 votes
1 answer
761 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 $...
Zara's user avatar
  • 578
2 votes
1 answer
96 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 ...
ATB's user avatar
  • 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$
gftyh's user avatar
  • 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, ...
dfdf1's user avatar
  • 85
2 votes
2 answers
82 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+...
Diego Gallo's user avatar
0 votes
4 answers
835 views

Stuck on middle step of proof that $a^{p(p-1)}=1 \pmod{p^2}$ [duplicate]

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 ...
Manny's user avatar
  • 129
2 votes
1 answer
205 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}...
Anna Naden's user avatar
2 votes
1 answer
228 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 ...
Ilan Alon's user avatar
4 votes
1 answer
128 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)...
user avatar
1 vote
0 answers
137 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:...
lsr314's user avatar
  • 15.9k
-1 votes
1 answer
121 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 ...
Aayam Mathur's user avatar
1 vote
1 answer
426 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$?
Monya Feldman's user avatar
3 votes
1 answer
209 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 ...
Emma Johnson's user avatar
1 vote
0 answers
85 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)...
Chanr13's user avatar
  • 27
10 votes
1 answer
344 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^...
Jeppe Stig Nielsen's user avatar
2 votes
0 answers
76 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 ...
user759001's user avatar
2 votes
1 answer
237 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\...
user759001's user avatar
2 votes
1 answer
148 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 ...
Augusto Santi's user avatar
2 votes
0 answers
90 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 ...
Tomáš Macháček's user avatar
1 vote
0 answers
80 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 ...
Safwane's user avatar
  • 3,854
3 votes
1 answer
100 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 ...
Safwane's user avatar
  • 3,854
0 votes
1 answer
230 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 (...
stepasite's user avatar
2 votes
1 answer
63 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 ...
Safwane's user avatar
  • 3,854
2 votes
1 answer
147 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......
진규영's user avatar