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
0 votes
1 answer
29 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^{...
user avatar
  • 21
0 votes
1 answer
43 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$$ ...
user avatar
  • 159
2 votes
1 answer
77 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 ...
user avatar
  • 33
1 vote
1 answer
24 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 ...
user avatar
  • 33
0 votes
1 answer
61 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. ...
user avatar
  • 1,399
1 vote
1 answer
62 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$, ...
user avatar
-1 votes
2 answers
201 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 ...
user avatar
3 votes
2 answers
76 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 ...
user avatar
  • 31
1 vote
2 answers
103 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^...
user avatar
  • 1,553
0 votes
0 answers
46 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 ...
user avatar
1 vote
2 answers
91 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 ...
user avatar
0 votes
0 answers
247 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 ...
user avatar
  • 1,399
-6 votes
1 answer
78 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) \...
user avatar
0 votes
1 answer
288 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 $...
user avatar
  • 568
2 votes
1 answer
82 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 ...
user avatar
  • 746
-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$
user avatar
  • 1
0 votes
2 answers
97 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, ...
user avatar
  • 85
2 votes
2 answers
73 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+...
user avatar
1 vote
4 answers
249 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 ...
user avatar
  • 131
2 votes
1 answer
125 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}...
user avatar
2 votes
1 answer
162 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 ...
user avatar
4 votes
1 answer
100 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
110 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:...
user avatar
  • 15.5k
-1 votes
1 answer
84 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 ...
user avatar
1 vote
1 answer
226 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$?
user avatar
3 votes
1 answer
106 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 ...
user avatar
1 vote
0 answers
41 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)...
user avatar
  • 27
10 votes
1 answer
308 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^...
user avatar
2 votes
0 answers
59 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 ...
user avatar
2 votes
1 answer
200 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\...
user avatar
2 votes
1 answer
94 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 ...
user avatar
2 votes
0 answers
66 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 ...
user avatar
1 vote
0 answers
77 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 ...
user avatar
  • 3,733
3 votes
1 answer
70 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 ...
user avatar
  • 3,733
0 votes
1 answer
150 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 (...
user avatar
2 votes
1 answer
59 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 ...
user avatar
  • 3,733
2 votes
1 answer
133 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......
user avatar
0 votes
2 answers
290 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 $
user avatar
  • 3
1 vote
2 answers
57 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}$$ $...
user avatar
  • 117
2 votes
0 answers
185 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! ...
user avatar
  • 4,935
3 votes
3 answers
386 views

Use Fermat’s little theorem to show that $8, 9, 10$ are not prime numbers

Use Fermat’s little theorem to show that $8, 9, 10$ are not prime numbers. I know that the theorem states: for all $a$ in $\mathbb Z$, if $p$ is prime and $p$ does not divide $a$ then $a^p = a$ mod $...
user avatar
  • 111
2 votes
2 answers
119 views

Remainder of Fermat's little theorem sum

With p being a prime number, what is the remainder of $$\sum_{k=1}^{p-1} {k^{p-1}}$$ divided by p ? I know that Fermat's little theorem states that for a prime number p, and a number A that is not ...
user avatar
  • 33
0 votes
1 answer
42 views

Let $A_p=a^{2^p}+b^{2^p}$. Prove that $(A_p,A_q)=1\forall p\ne q$

Let $a,b\in N^*$ such that $2\mid ab$ and $(a,b)=1$. Consider $A_p=a^{2^p}+b^{2^p}$ show that $$(A_p,A_q)=1\forall p\ne q$$ Let $(A_p,A_q)=d(d\in \mathbb{Z})$ then i will prove $d=1$ From $2\mid ab$...
user avatar
  • 413
0 votes
1 answer
88 views

There exist no Fermat numbers which are cubes

Prove that there exist no Fermat numbers which are cubes. How does one go about proving this? I think the problem is from an olympiad. I've succeeded in proving that no Fermat numbers are squares, ...
user avatar
  • 51
3 votes
1 answer
88 views

Can we prove that $(2^{2^{n}}+1)+(2^{2^{n-1}}+1) -1$ have at least $n$ different prime divisors

My point was to prove it using induction. Then for $n=1$ it is true, for n = k it is also true so we assume that $ \color{Red}{ 2^{2^{k}} + 2^{2^{k-1}} + 1}$ has at least k different prime divisors ...
user avatar
  • 119
1 vote
1 answer
41 views

An elaboration of a step in an example.

A part of the example is given below: Example 9.7. Let us turn to a quite different application of these ideas. At an earlier stage, it was observed that if $F_n = 2^{2^n} + 1$, $n > 1$, is a ...
user avatar
  • 3,064
3 votes
1 answer
240 views

Fermat's last theorem. Where is the mistake?

I am trying something with Fermat's last theorem: Maybe I am totally wrong about this and so I wanted to post it here for you guys to try and check it. Fermat's last theorem states that you will not ...
user avatar
  • 33
1 vote
2 answers
77 views

Why is it that exponents that are divisors of φ(N) capable of generating the identity element as a power when N is prime?

Let $p=x$ where $a^x \equiv 1\pmod N$. When $N$ is prime I can check whether $p=N-1$ and if it is, there are a full set of remainders. However, if $p<N-1$, I need to keep checking. For example, if $...
user avatar
  • 189
0 votes
1 answer
794 views

If the order of a number (mod n) equals n-1 then n is prime? [duplicate]

I have trouble in understanding the last part of the sufficiency proof of Pépin´s Test (https://en.wikipedia.org/wiki/Pépin%27s_test). "In particular, there are at least least F_{n}-1 numbers below ...
user avatar
1 vote
1 answer
21 views

Show that $a$ generates the group of units $(\Bbb{Z}/F_n\Bbb{Z})^\times$

Let $F_n=2^{2^n}+1$ be a Fermat prime and let $a\in\Bbb{Z}$ such that $F_n\not| a$ and $a$ is not a quadratic residue modulo $F_n$. I want to show that the class $a+(F_n)$ generates the group of ...
user avatar
  • 5,991