Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

1
vote
1answer
15 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 ...
-5
votes
2answers
73 views

fermat's Lasst Theorem has an error? [on hold]

I have a proof of Fermat's Last Theorem that is a little more than a page long. It uses simple math but I can't find the error in the proof. What is the error in the proof? FLT for powers of $n$ odd,...
1
vote
2answers
43 views

If $q$ is a Fermat prime, is $\sigma(q^k)/2$ a square if $k \equiv 1 \pmod 4$?

In what follows, let $\sigma(x)$ denote the sum of divisors of the positive integer $x$. A number of the form $M = 2^{2^m} + 1$ is called a Fermat number. If in addition $M$ is prime, then $M$ is ...
0
votes
1answer
44 views

Use Fermat’s Theorem to prove Euler’s Theorem in the case m = pq. with p and q being two distinct prime numbers

If $p$ is a prime and $p$ does not divide $a$, then $$a^{p-1} \equiv 1 \pmod{p}.$$ Since $p$ is prime, the fact that $p$ does not divide a means that $a$ and $p$ are relatively prime. Also, $\varphi(p)...
0
votes
1answer
99 views

Fermat's Little Theorem & Euler's Theorem

Make a table showing the values of $a, a^2, a^3, a^4, a^7, (a^3)^7$ modulo 33 for 0 ≤ a ≤ 16, expressing the entries as integers in the interval [−16, 16]. Explain why two of the columns are the same. ...
2
votes
1answer
128 views

Is $10^{2^{21}}+1$ known to be composite?

I looked at the generalized Fermat-prime-numbers. According to factordb, the case $$10^{2^{21}}+1$$ is unknown. Neither a factor is displayed nor $C$ for "composite". Hence my question : Is $$10^{2^...
2
votes
2answers
44 views

Prove $n$ having to be an exponent of 2 for $b^n + 1 =$ a prime number

I have been having problems finding a solution for this problem and honestly have no ideas left how to solve this, please help. Assume that $b^n + 1= $ a prime number for some integers $b,n$ where $b&...
0
votes
1answer
79 views

If prime $p$ such $p|F_{n}(n\ge 2)$, show that $p\equiv \pm 2 \pmod 5$

Let $p$ be a prime number and $$p|F_{n}, n\ge 2$$ where $F_{n}=2^{2^n}+1.$ Show that $$p\equiv \pm 2\pmod 5.$$ I have proved $$F_{n}\equiv 2\pmod 5,$$ because $$F_{n}=2^{2^n}+1=(2^2)^{2^{n-1}}+1\...
0
votes
1answer
69 views

Show that the term $xy+1$ is a perfect square.

Let $F_k$ denote the $k$th Fermat number $2^{2^k}+1$. If $$A=\{F_{2n}, \ F_{2n+2}, \ F_{2n+4}, \ 4F_{2n+1}F_{2n+2}F_{2n+3}\},$$ then I want to show that for $x,y\in A$ with $x\neq y$ the term $xy+1$ ...
1
vote
1answer
121 views

Question about a kind of generalized Fermat numbers

The present question is directly inspired by this one. Let $\alpha$ be a unit in the ring of quadratic integers of a real quadratic field, or, in less sophisticated words: $$\alpha=\frac{a\pm\sqrt{...
0
votes
2answers
54 views

I am stuck on Fermat's Little Theorem. I know how to apply it, but does it apply here $15^{48}$ mod $53$.

I can't seem to figure out this problem. I can factor to reduce the number, but this is too time consuming. Isn't FLT suppose to help here? Can someone provide clarification please? FLT problem
0
votes
1answer
145 views

Proving $a^{n-1} \equiv 1 \mod n $ when n is not prime.

Let $t∈\Bbb N$ and let $x=6t+1, \:y=12t+1$ and $z=18t+1$. $x, y$ and $z$ are all primes and let $n=xyz$. Prove that $a ^{n-1} \equiv 1 \pmod n\;$ whenever $ a∈\Bbb Z$ and $\gcd(a,n) = 1$. I have ...
1
vote
1answer
35 views

Prove that $2^{2^n}-1$ has at least n prime divisors

I know that it is Fermat number and that all Fermat numbers are coprime, but I have no idea how to continue
1
vote
0answers
53 views

Generating prime factors of a certain congruence?

I'm aware that prime factors of $n^2+1$ take the form $4k+1$. It's also well known that factors dividing $\frac{a^p \pm 1}{a \pm 1}$ will be congruent to $2kp+1$. Fibonacci and some other recurrence ...
0
votes
1answer
72 views

Primes from Generalised Fermat Numbers [closed]

Consider the number $(2m)^{2^n}+1$ where both $m$ and $n$ are positive integers. Can it be shown that for any given $n$, there exists an $m$ such that $(2m)^{2^n}+1$ is a prime number. Edit: It ...
1
vote
1answer
138 views

Nontrivial integer solutions of $ a^3+b^3=c^3+d^3$

How can we obtain a set of nontrivial solutions of $$ a^3+b^3=c^3+d^3, $$ for $a,b,c,d\in \mathbb{Z}$ where $(a,b)\neq (c,d)$ and $(a,b)\neq (d,c)$. Say in the range that $|a|,|b|,|c|,|d| \in [...
2
votes
3answers
73 views

Show that $\pi\left(n\right)\geq\log_{2}\left(\log_{2}\left(n-1\right)\right)$

I need to show that $$ \pi\left(n\right)\geq\log_{2}\left(\log_{2}\left(n-1\right)\right) $$ where $\pi\left(n\right)=\left|\left\{ p\mid p\text{ is prime and }p\leq n\right\} \right|$ Now i somehow ...
6
votes
1answer
58 views

Is my proof correct on how $k$ must be a power of $2$? Are there other proofs?

So I was looking at the Fermat Primes. These are primes of the form $2^k+1$ for a natural number $k$, such that I define by $\mathbb{N}:=\big\{1,2,3,\ldots\big\}$ and $0\notin \mathbb{N}$. We denote ...
0
votes
1answer
24 views

Nature of the prime factors of generalised Fermat numbers

I have an example I am trying to prove but I can't quite see the trick and would appreciate some help: Suppose p is a prime factor of $10^{2^k} +1$. Show that $p \equiv 1$ (mod $2^{k+1}$). (Also: ...
0
votes
1answer
29 views

Prove $n\geq 3$ is prime or that the largest non-trivial factor of $n$ is at least $3\sqrt{n}$

Given $a^2 − n$ is not a perfect square for any integer $a$ in the interval $\tfrac23\sqrt{n} < a < 2\sqrt{n}$, prove $n \geq 3$ ($n$ odd) is prime or the largest non-trivial factor of $n$ is at ...
0
votes
1answer
59 views

how can I prove that 29341 is not a prime number, with Fermat [closed]

I know that the formula is:enter image description here
5
votes
2answers
156 views

Easiest way to check whether the number is prime or not

Recently I came across a YouTube video which explains the easiest way to check whether the given number is prime or not the equation was: $$\frac{2^x - 2}{x}$$ According to that video if $x$ is a ...
1
vote
1answer
53 views

On miscellaneous questions about perfect numbers III

This is a wild guess about odd perfect numbers. Thus you can see it as an exercise and not as a serious conjecture. I add here the MathWorld's reference dedicated to odd perfect numbers. Question. ...
1
vote
1answer
70 views

Show that all Fermat numbers pass the base $2$ test (pseudoprime).

I realize that there is a similar post to this, but that post included a hint which we were not given. Also regarding that hint, I'm just wondering how someone could find it out for themselves. Here ...
2
votes
0answers
48 views

On the equation $\varphi(2+\varphi(x))=2^{y-1}$, where $\varphi(n)$ denotes the Euler's totient function

I don't know if was in the literature a characterization of the solutions for pair of integers $(x,y)$ of the equation $$\varphi(2+\varphi(x))=2^{y-1},\tag{1}$$ where $\varphi(n)$ denotes the Euler's ...
1
vote
1answer
64 views

A question about proving distinct Fermat numbers are relatively prime

I am reading Elementary Number Theory with Programming, and bump into the proof of "The Fermat numbers $F_n$ and $F_m$ where m ≠ n are relatively prime.": Theorem: The Fermat numbers $F_n$ and $...
1
vote
2answers
41 views

towers of 2 and primes, generation s of big primes by iteration of the function $2^{x}$

let be $2+1=3 $ , $ 2^{2}+1=5 $ , $ 2^{2^{2}}+1= 17 $ apparently what would be the first counterexample ?? is almost true that towers of 2 (iterations of the function $ 2^{x}$ will give big ...
0
votes
1answer
94 views

Modulo Exponential based on Fermat's little theory?

I come from Computer Science background. In order to proceed with my question, I want to clarify that we use modular exponential as part of RSA encryption; and please be warned, I'm weak at maths :) ...
0
votes
1answer
129 views

$2$ cannot be a primitive root of a prime $F_n$

$2$ cannot be a primitive root of a prime $F_n = 2^{2^n} + 1$ where $n\ge 2$ I've understood that the fact that $F_n \equiv 1 \pmod{8}$ for $n\ge 2$ might be helpful here, but I don't see how (Though ...
0
votes
1answer
46 views

Does there exist $a,b,c\in \mathbb{R}$ such that for all $n$, $a^{2n+1}+b^{2n+1}=c^{2n+1}$?

Let $a,b,c \in \mathbb{R}$, $n \in \mathbb{N}$ Is it possible that there are a,b,c that fulfill the following equation for every $(2n+1)$? $a^{2n+1}+b^{2n+1}=c^{2n+1}$ $(i.e \quad a^3+b^3=c^3, a^5+...
0
votes
1answer
120 views

Use recurrence relation Fermat numbers to show that the set of prime numbers is infinite

I'm working on some proofs on a recurrence relation with Fermat numbers. a). Prove with Fermat numbers $f_n = 2^{2^n} + 1$ that: $$ f_0 \cdot f_1 \cdot f_2 \cdot f_3 \cdots f_{n-1} = f_n - 2$$ b). ...
1
vote
1answer
60 views

Number of integers (less than $n$) that are divisible by a prime factor of $n$

Given $n$ as $$n = \prod_{i = 1}^{m} {p_i}^{e_i} = {p_1}^{e_1} {p_2}^{e_2} \cdots {p_m}^{e_m}$$ where where the $p_i$ are distinct prime numbers. My question is how the following statement is ...
0
votes
1answer
385 views

How to prove n^k ≡ n mod 5 if and only if k ≡ 1 mod 4, for all integer n and k is natural?

I do believe that it has something to do with Fermat's little theorem, and I can prove the backward relationship, but how to prove the forward if? like is N^k-1 necessarily be n ^ 4m?
1
vote
3answers
52 views

Proof about Fermat number without induction

I want to show that $7 \mid (F_{2k + 1} + 2)$ where $k \in \mathbb{N_0}$ and $F_n := 2^{2^n} + 1$. I was able to proof this using induction, but was wondering if there is a more direct approach? Here ...
1
vote
1answer
269 views

Use Fermat's little theorem to compute x^y^z mod p (where p is prime)?

I'm new to Fermat's theorem (a, and I am familiar with how to use it in basic cases with relatively large numers (i.e. 2^345 mod 31). I was given the question to find 4^(2^2006), and found myself ...
1
vote
1answer
64 views

How many primes are in this set?

From an old number theory book: Consider all numbers of the form $$ x_n={2^n+1}, n=0,1,2,\dots $$ How many of them are prime? Mathematica gave $x_0=2,x_1=3,x_2=5,x_4=17,x_8=257, x_{16}=65537$ and is ...
2
votes
2answers
62 views

If $F_m = 2^{2^m} + 1$ is prime (with $m \geq 1$), does it follow that $3 \mid \frac{F_m + 1}{2}$?

If $$F_m = 2^{2^m} + 1$$ is prime with $m \geq 1$, does it follow that $$3 \mid \frac{F_m + 1}{2}?$$ I have verified this to be true for $1 \leq m \leq 4$.
2
votes
2answers
707 views

$2^n + 1$ is prime $ \implies n$ is a power of $2$

I was wondering why I can't do this this way by proof by contradiction of the contrapositive. So I want to prove $$2^n + 1 \quad \text{is prime} \implies n = 2^k \quad \text{for some} \ k\in \mathbb{Z}...
1
vote
2answers
383 views

Induction on Fermat Numbers: $F_n = \prod_{j=0}^{n-1}F_j+2$

Is the Following Proof Correct? Theorem. Given that $\forall n\in\mathbf{N}(F_n = 2^{2^n}+1)$ show that the following is true $$\forall n\in{1,2,3...}\left(F_n = \prod_{j=0}^{n-1}F_j+2\right)$$ Proof....
3
votes
1answer
85 views

primality of $\frac{(2^{19}+1)}{3}$ and $\frac{(2^{23}+1)}{3}$

This is from an exercise in Burton's Number theory book. I have a hard time solving this. How could we prove that $\displaystyle\frac{(2^{19}+1)}{3}$ and $\displaystyle\frac{(2^{23}+1)}{3}$ are primes....
-1
votes
2answers
213 views

$3^{15} \mod 17$ I would like using Fermat theorem and doing something like this $\frac{3^{16}}{3} \mod 17$ that is possible?

$$3^{15} \mod 17$$ $$3^{15} \mod 17 \implies \frac{3^{16}}{3} \mod 17$$ It seemed to me the correct result would be $\frac{1}{3}$.
0
votes
1answer
106 views

Euler Totient of Fermat Numbers

I was working on a problem which asks me to prove that the Euler Totient of a Fermat number is always a perfect square. I found out that every factor of the Fermat number is of the form, $\ k.2^{2^{...
1
vote
0answers
75 views

Non prime modulus of prime powers

Given a function $f(x,n) = x^{x^{x^{x}}}$ where $n = \text{how many powers of }x$, how to find value of $f(x,n) \bmod k$, where $k < x$ and $k$ can be prime or not prime and has large values. For ...
0
votes
1answer
90 views

Modular Congruence of the Fermat Numbers

I'm just trying to study for exam season and got stuck on a question; which I'm not really sure how to tackle.. looking through all my lecture notes I just can't seem to see what techniques are ...
-3
votes
1answer
106 views

Prove there are no positive integers $x$ and $y$ such that $x^3 + y^3 = 10^3$. [duplicate]

I am familiar with Fermat's Last Theorem that there are no integers such that $x^3+y^3=z^3$, but I need a simpler proof that demonstrates that fact when we know that $x$ and $y$ are positive, and $z=...
4
votes
1answer
196 views

What is the connection between Fermat's Little Theorem and “Fermat Liars”?

I know that Fermat's Little Theorem states that if $p$ is prime and $1 < a < p$, then $a^{p-1} \equiv 1 ($mod $p)$. I also know that a Fermat Liar is any $a$ such that $a^{n-1} \equiv 1 ($mod $...
1
vote
1answer
1k views

Show that every composite Fermat number is a pseudoprime base 2.

Question: Show that every composite Fermat number $F_m=2^{2^m}+1$ is a pseudoprime base 2. Hint: Raise the congruence $2^{2^m}\equiv-1($mod $F_m)$ to the $2^{2^m-m}$th power. Even with the hint, I'm ...
0
votes
1answer
289 views

solving ax +b mod p = y

How do I solve ax+b mod p = y, with p being prime? What I have gotten so far is ax = y - b (mod p) ...
0
votes
2answers
185 views

Constructible n-gon proof using Fermat primes

The regular $n$-gon is constructible by ruler and compass precisely when the odd prime factors of $n$ are distinct Fermat primes. Prove that in this case, $φ(n)$ is a power of $2$. Where $φ(n)$ is ...
0
votes
1answer
99 views

Odd Fermat primes proof in an $n$-gon

The regular $n$-gon is constructible by ruler and compass precisely when the odd prime factors of $n$ are distinct Fermat primes. Prove that in this case, $φ(n)$ is a power of $2$. Where $φ(n)$ is ...