Stack Exchange Network

Stack Exchange network consists of 174 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 [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.

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