Questions tagged [prime-numbers]
Prime numbers are natural numbers greater than 1 not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.
8,224 questions
1
vote
2answers
34 views
Proof relatively prime numbers
Let $p,q,r$ be three distinct prime numbers and $m = p*q*r$.
How many of the numbers {$1,2,...,m$} are relatively prime to $m$?
I tried to do it for:
a) $m=2*3*5=30$,
b) $m=2*3*7=42$,
c) $m=3*5*...
0
votes
2answers
36 views
Infinitely many consecutive primes with difference greater than 2. [on hold]
Let $p_k$ be the $k$-th prime number. Show that there are infinitely
many $k$ such that
$$p_{k+1} − p_k > 2$$.
Suppose If this is not true then won't that contradict the twin-prime conjecture?
0
votes
0answers
16 views
Modified Hecke Dirichlet Series
Let $\lambda$ be the normalized Hecke Eigenvalue of a primitive cusp form $f$. I have a Dirichlet series $\sum_{n\geq1}\lambda(p^ln)n^{-s}$. How can I pull out the factor $p^l$ in a way that only $\...
1
vote
0answers
26 views
Using least common multiple to prove there exists a prime between $2x$ and $3x$
Let $\text{lcm}(x)$ be the least common multiple of $\{1,2,3,\dots, x\}$.
Hanson showed that $\text{lcm}(x) < 3^x$
I'm wondering if the following argument is valid for showing that there is ...
3
votes
1answer
31 views
For what primes $p \nmid \gcd(a,b,c)$ does $p \mid a+b+c \implies p \nmid a^2+b^2+c^2$?
Let us have prime $p$ such that $p \nmid \gcd(a,b,c)$ and $p \mid a+b+c$. For what primes is it then impossible for $p \mid a^2+b^2+c^2$ ?
One example of such a prime is $p=5$:
If $5 \mid a^2+b^2+c^...
0
votes
1answer
32 views
(Soft Question) Largest known semiprimes with no known factors
Is there a list, similar to prime numbers and probable primes, of the largest semiprimes with unknown factors? Is there a list of numbers that are either semiprime or prime, with no known factors? Is ...
3
votes
1answer
46 views
Pair up {1..2n} that the sums of each pair are different primes.
Pair up $\{1..2n\}$ that the sums of each pair are different primes.
I found 9 examples:
$\{(1,2)\},$
$\{(1,2),(3,4)\},$
$\{(1,2),(3,4),(5,6)\},$
$\{(1,4),(2,5),(3,8),(6,7)\},\{(2,3),(1,6),(4,7),(...
0
votes
0answers
27 views
How can I find the exponent $n$ efficiently?
Denote $$z=(2^{19}-1)\cdot10^6+2^{18}-1$$ $$a=ord_2(z)$$ $$b=ord_{10}(z)$$
The object is to find a positive integer of the form $$n=ka+19$$ with positive integer $k$ such that $$m=f(n)=\lceil(n-1)\...
0
votes
1answer
14 views
Show that each subgroup generated by prime integer is maximal in $(\Bbb Z, +)$.
Show that each subgroup generated by prime integer is maximal in $(\Bbb Z, +)$.
Here I know that we can prove maximal by showing its quotient group is simple.
But how can I approach "each subgroup ...
1
vote
1answer
33 views
Proving $ord_p(ζ_p-1)=1/(p-1)$
After proving this, I was able to deduce an even more general result that $ord_p(ζ_p-1)=ord_p(ζ_p^2-1)=...=ord_p(ζ_p^{p-1}-1)$. Now, according to Lubin, $ord_p(ζ_p-1)$ should be $1/(p-1)$, but this ...
0
votes
0answers
14 views
Thoughts on Lehs conjecture $\forall n>2\in \mathbb N\exists a,b\in \mathbb N$ such that $a+b=n\land (a+ab+b)\in \mathbb P$. Lehs comet?
Lehs conjectured here that $\forall \ n>2\in \mathbb N,\exists\ a,b\in \mathbb N$ such that $a+b=n\land (a+ab+b)\in \mathbb P$. In comments, Crostul restated this as $\forall \ n\ge 4\in \mathbb N,...
2
votes
3answers
35 views
Showing the lemma $\operatorname{ord}_p(1+ζ_p)=0$ if $p>2$
Just to give some background regarding my motivation, I'm trying to prove a lemma to help me solve How do we prove p-order of $g_k$ is $\frac {k} {p-1}$?
Let $Z_p$ denote the p-adic integers, and let ...
2
votes
1answer
33 views
RSA: Show how to factor $n$, the product of two primes
As an exercise in my discrete mathematics textbook, for my first-year course, the following question is asked, on the topic of RSA encryption:
Show that we can easily factor $n$ when we know that $n$ ...
4
votes
6answers
61 views
Prove that if $p$ is prime and $p\le$ $n$ then p does not divide $n!+1$.
Prove that if $p$ is prime and $p\le n$ then $p$ does not divide $n!+1$.
I know that in this case since $p$ divides $n!$, then it does not divide $n!+1$ but I am not sure how to show this.
0
votes
1answer
49 views
A simple equation with a complicated property
Let, $\Bbb{P}$ denote the set of all odd prime numbers and $\Bbb{N}$ be the set of all natural numbers. Let, $2a,2b$ be two even numbers both greater than $4$.
Define, $A=\{(p,q)\in\Bbb{P}\times\Bbb{...
0
votes
0answers
48 views
About $\varphi(n)$ I don't know how to get? [on hold]
$$
\sum_{n\mid m}\sum_{d\mid n}d\varphi\left(\frac{n}{d}\right)
=\sum_{n\mid m}\sum_{i\mid \frac{m}{n}}n\varphi(i)\\
=\sum_{n\mid m}n\frac{m}{n}=m\sum_{n\mid m}1
$$
so, how to get this?
$$
\sum_{n\...
12
votes
2answers
111 views
The general proposition of Fermat
In his letter to Frenicle, dated 18th October, 1640, Fermat states the following (Point 8, translated) :
If you subtract $2$ from a square, the remaining value cannot be divided by a prime which ...
1
vote
1answer
24 views
In a perfect number $2^{p−1} \times (2^p − 1)$, the ratio of $p$ to the digits in its perfect number approaches $\log(10) / \log(4)$?
I was reading about Mersenne primes and perfect numbers, and how the expression $2^{p−1} \times (2^p − 1)$, where $p$ is any prime number, can be used to generate perfect numbers when $2^{p−1}$ is a ...
4
votes
2answers
95 views
For all $n>1$ there are positive $a+b=n$ such that $a+ab+b\in\mathbb P$
For all integers $n>1$ there are positive integers $a,b$ such that $a+b=n$ and such that $a+ab+b\in\mathbb P$.
Tested for all $n\leq 1,000,000$. Hopefully, someone can explore and explain the ...
2
votes
0answers
26 views
Existence of divisor of multiple of primes congruent to 1 mod 4
Show that for every prime $p\equiv 1\pmod 4$, there exists positive integers, $n,m$ such that
$$n(4m-p)-1\mid mp$$
Or equivalent, if we let $m= \frac{p+4k+3}{4}$,
$$n(4k+3)-1\mid p\left(\frac{p+4k+...
2
votes
1answer
26 views
Given an odd integer, $a$ does $\gcd(a,p-1)=1$ has infinitely many prime $p$ solutions?
Given an odd integer, $a$ does $\gcd(a,p-1)=1$ has infinitely many prime $p$ solutions?
One can argue that there are infinitely many numbers $x$ satisfies $\gcd(a,$x$)=1$. How to argue that there ...
1
vote
0answers
35 views
Can I find the next prime with sufficient small residue efficiently?
Suppose, positive integers $N,a,b$ are given.
The object is to determine the smallest prime $p$ larger than $a$ such that $N$ modulo $p$ is smaller than $b$.
Can I determine $p$ efficiently (...
1
vote
1answer
71 views
+50
Upper bound for a ratio of two least common multiples
Let $\text{lcm}(x)$ be the least common multiple of $\{1,2,3,\dots,x\}$
Let $x\#$ be the the primorial for $x$.
It occurs to me that for $x \ge 10$:
$$\frac{\text{lcm}(x^2+x)}{\text{lcm}(x^2)} < ...
0
votes
1answer
39 views
A simple problem on prime numbers [closed]
Give a demostration of:
$\forall N>1$, $\exists k\in \{0,1,2,...,N-1\}$ such that:
$N^{2}-k^{2}=p_{1}p_{2}$, where $p_{1}$ and $p_{2}$ are primes.
0
votes
2answers
121 views
Searching for Goldbug Numbers
A Goldbug Number of order k is an even number 2n for which there exists some k order subset of the prime non-divisors of n $2 < p_1 < p_2 < p_3 < \cdots < p_k < n$ such that $(2n-p_1)...
1
vote
1answer
39 views
How to prove the existence of a prime number with elementary method?
Suppose $A>5$ is an integer and there exists a prime number $p$ such that $A-2\leq p^2<A$.
Show that there exists at least one prime number $q$ such that $p<q<A$.
This seems to be ...
6
votes
1answer
78 views
A prime $p$ of the form $4k+1$ implies that $k^k \equiv 1 \mod p$?
I can not prove this statement that seems related to Fermat's little theorem. I would appreciate indications to prove this result (suggestions, links, etc.)
Following @mark-bennet hints:
$4k \equiv -...
1
vote
1answer
20 views
How one can get an estimate or a range for the integer $n$
Let $(p_{n})_{n≥1}$ be the sequence of prime numbers. I have an inequality of the form:
$$p_{n}<a$$
where $a$ is a real number.
My question is: How one can get an estimate or a range for the ...
2
votes
0answers
44 views
Polynomial divisor in $\mathbb{Z}_p[x]$?
Q: Find an odd prime $p$ for which $x-2$ is a divisor of $x^4 + x^3 + 3x^2 + x + 1$ in $\mathbb{Z}_p[x]$.
I would rather not go through the Euclidean Algorithm for every mod $p$. Is there another way ...
2
votes
0answers
27 views
Might there be a Skewes number for semiprimes?
Briefly the question here is whether there is or could be a theorem analogous to that of Littlewood for semiprimes (generalized prime numbers which are products of two primes, repetitions allowed), ...
1
vote
1answer
36 views
Find three prime numbers
I have to find three prime numbers where, the product of them is equal to seven times of sum of them.
So I wrote the equation:
$x$-1st of them;
$y$-2nd;
$z$-3rd;
$xyz=7(x+y+z)$
${xyz\over 7}=x+...
1
vote
1answer
52 views
Primes dividing $x^2+xy+y^2+1$
Is there infinitely prime numbers $p$ such that $p$ divides $x^2+xy+y^2+1$ for some integers $x,y \in \Bbb Z$ ?
I can show that every prime $p$ divides $x^2+y^2+1$ for some integers $x,y \in \Bbb ...
-1
votes
0answers
38 views
If $|G|=p^nm$ where $\text{gcd}(p,m)=1$ and $|G|<m!$, then can $|G|$ be simple?
I think my professor had a type-o on recent homework. He claims that if $G$ is a group and $p$ prime, then if the title's conditions hold we must have $G$ not simple. This doesn't seem correct to me, ...
1
vote
1answer
42 views
Finding primes p such that $3x^2=2$ has no solution modulo p
I am not sure how to do this. I know about Legendre symbols and reciprocity but how do I deal with the 3 coefficient?
5
votes
0answers
85 views
Primes of the form $p=x^4+y^4$
Are there infinitely many prime numbers $p$ such that
$$p = x^4+y^4$$
for some $x,y \in \Bbb Z$ ? What if we only require $x,y \in \Bbb Q$ ?
I know that $p = a^2+b^2$ with $a,b \in \Bbb Q$ iff $p = a^...
5
votes
1answer
65 views
If $p=a^2+b^2$ prove these consequences about $\big(\!\frac{a}{p}\!\big)$
Suppose odd prime $p=a^2+b^2$, and $a$ is odd and $b$ is even. Prove that if $b\equiv2\pmod4$, then $\left(\dfrac bp\right)=-1$ and if $b\equiv0\pmod4$, then $\left(\dfrac bp\right)=1$.
What I have ...
5
votes
4answers
351 views
Use Fermat's Theorem to prove 10001 is composite
I need to use Fermat's Theorem to prove that 10001 is not prime. I understand that I just need to find a counterexample where $a^{10000}$ mod 10001 = 1 mod 10001 does not hold true, but this seems ...
0
votes
0answers
24 views
Bases for deterministic Miller-Rabin primality test
Miller-Rabin primality test can be made deterministic when the number $n$ is small, for example "if $n < 2047$, it is enough to test [with base] $a = 2$".
How are those bases found? By brute force?...
0
votes
1answer
56 views
Fermat's Little Theorem and Carmichael Numbers
Fermat's little theorem states that if $p$ is a prime number and $a$ is a positive integer, then $p|a^p-a$.
However, the converse is false, that is, for integers $a$ and $p$, if $p|a^p-a$, then $a$ ...
0
votes
0answers
33 views
Fraction of a numbers digit permutations that are prime
Calculate the following number
$$\sup \{x\in[0, 1] \space | \space \#A_x = \infty \}$$
Where $A_x = \{n\in \mathbb{N} \space | \space \text{the fraction of $n$'s digit permutations that are prime }...
0
votes
0answers
23 views
How to get $p^{\alpha} \ \mid \ o \left( H \right)$ from $p^{\alpha \ + \ \Bbbk } \ \mid \ n \ o \left( H \right)$?
I was studying "A Formal Proof of Sylow’s Theorem" by FLORIAN KAMMÜLLER and LAWRENCE C. PAULSON.
But I did not find a way to get $p^{\alpha} \ \mid \ o \left( H \right)$ from $p^{\alpha \ + \ \Bbbk } ...
1
vote
1answer
40 views
Gauss sum possible typo
Let $ψ: \mathbb{F_p} \to Z_p$ with the property $ψ(a+b)=ψ(a)ψ(b)$ where $Z_p$ denotes the p-adic integers. Assume further that $ψ$ is not trivial.
I'm trying to follow my professor's work, but I ...
2
votes
0answers
43 views
Simplifying radicals without using prime factorization
Is there an easy way to simplify radicals?
For example, take the case of $\sqrt{252}$. We can the find prime factorization of $252$ as $252=2\times 2\times 3 \times 3\times 7$ and thus we get $\sqrt{...
4
votes
1answer
91 views
How to approach this sequence? (elementary number theory)
Given is the following sequence: $a_1 = 1$ and $a_n$ equals the biggest prime divisor of $1+ a_1*\dots*a_{n-1}$ .
It is then claimed: $11$ does not occur in this sequence.
How can one approach this ...
1
vote
1answer
43 views
Infinite sequence of integers has infinitely many prime divisors
Problem: For a sequence $\{a_i\}_{i\ge 1}$ consisting of only positive integers, prove that if for all different positive integers $i$ and $j$, we have $a_i \nmid a_j$ , then
$$\{p\colon p \text{ is a ...
4
votes
1answer
61 views
Is the conductor of an L-function F the absolute value of the discriminant ofsome number field related to F?
In the theory of automorphic forms, ramified primes of an L-function divide the so-called conductor thereof. On the other hand, one can define for a number field $ K $ an integral invariant $ \...
0
votes
0answers
67 views
Why are these two groups not isomorphic?
I am trying to understand a proof (from the German book "Einführung in die Kryptografie" by Johannes Buchmann) that there are at most $(n-1)/4$ non-witnesses against the primality of $n$ in the Miller-...
1
vote
0answers
57 views
Questions about a proof of the error-bound of the Miller-Rabin-Test
I am trying to understand a proof (from the German book "Einführung in die Kryptografie" by Johannes Buchmann) that there are at most $(n-1)/4$ non-wittnesses against the primality of $n$ in the ...
0
votes
0answers
17 views
Partial harmonic sums with denominators from a fixed set of primes
It is well known that the harmonic sum $\sum_1^\infty \frac{1}{n}$ diverges to infinity, and more over that we can approximate using the integral of $\frac{1}{x}$ to get that $\sum_1^N \frac{1}{n} \...
2
votes
3answers
89 views
Elementary Number Theory: Show that $3^{10}\equiv 1 \pmod{11^2}$.
As the title says, I need to show $3^{10}\equiv 1 \pmod{11^2}$. I'm currently practicing some problems related to Fermat's little theorem and Wilson's theorem, and things were going fine but I am ...
