# Tagged Questions

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.

18 views

### Prove that the product of the primitive roots modulo the prime p is congruent to 1 modulo p if p > 3? [duplicate]

Prove that the product of the primitive roots modulo the prime p is congruent to 1 modulo p if p > 3. Just started going over primitive roots in class and a bit lost with this question. I do know ...
58 views

49 views

### Totien-Sum: why GCD( {n}/d, q/d) = 1; implies Sum{Totient(d/q) } = q

Have seen answer to this question. still don't understand.. Totient sum is defined: q = Sum(Totient (d) ); sum on all d : d|q More specific; The proof has these steps: 1. If d is a divider ...
53 views

### Primality testing though trial division.

I am having difficulty to understand this statement mentioned here: Remember that any composite integer n is build out of two or more primes n = P * P … P is largest when n has exactly two ...
34 views

### How can I prove that a linear recurrence $x_{n+1} = αx_n - β$ will contain a composite number in the sequence?

I'm working on a homework problem about finite automata and I got stuck trying to prove a fact about prime numbers that I think should be true. Given a prime $p$ and integers $α$ and $β$, can I show ...
33 views

### Find a prime $p>5$ such that $x^2 +1$ is reducible in $\mathbb Z_p[x]$

Find a prime $p>5$ such that $x^2 +1$ is reducible in $\mathbb Z_p[x]$. Can anyone please give me some hints as to how I can go about finding this value of $p$?
46 views

### Sum of the reciprocal of the prime-position primes.

The primes are $2, 3, 5, 7, 11, 13...$ The sum of the reciprocals of the primes diverges, proven by Euler: $$\sum_{n=1}^\infty{\frac{1}{p_n}}=\infty$$ Here, $p_n$ is the $n$-th prime. I'm asked to ...
33 views

### Compositeness test for Wagstaff numbers

Is this proof acceptable ? Definition Let $W_p=\frac{2^p+1}{3}$ with $p$ prime and $p>3$ . Theorem If $W_p$ is prime then $7^{\frac{W_p-1}{2}} \equiv -1 \pmod {W_p}$ Proof Let $W_p$ be a ...
74 views

### Primes Between Squares of Primes

Is this problem still open? I know that Henri Brocard conjectured that there are at least four primes in the interval between each pair of consecutive squares of primes from nine onward. ...
95 views

### Fibonacci Numbers and Legendre symbol

How to prove congruence below ? $$F_{p-\left( \frac{5}{p}\right)} \equiv 0 \pmod p$$ Where $\displaystyle \left( \frac{}{}\right)$ is legendre symbol, and $\displaystyle p$ is a prime number.
50 views

### How can I solve this using prime factors?

I'm stuck with this problem: $2^x \cdot 3^3 \cdot 26^y = 39^z$ for $x, y, z \in \mathbb{N}$. I know that there isn't a natural solution for the equation, but I need to "prove" it using prime factors. ...
44 views

### Prove, by giving an example , Fermat's Little Theorem

Prove, by giving an example, that, if n is not prime, a≠0(mod n) then it is not necessarily true that { [1]n,[2]n.........[n-1]n} = {[a.1]n,[a.2]n,.......[a.(n-1)]n} could you give me any hint to ...
92 views

### example, that Wilson's Theorem is not necessarily true

Show by an example, that Wilson's Theorem is not necessarily true if $p$ is not prime. (In fact, it is not hard to show that it is never true if $p$ is not prime, but I am not asking you to do that.) ...
24 views

### Calculating the difference of the factors of a semiprime

Let there be a semiprime $N=p q$ where $p$ and $q$ are prime numbers. If the value of $N$ is given, is there any way to calculate the value of $(p-q)$. If not exactly then approximately ? Update : ...
58 views

### Compositeness test for repunits

Is this proof acceptable ? Definition Let $R_p=\frac{10^p-1}{9}$ with $p$ prime be a repunit number . Theorem If $R_p$ is prime then $7^{\frac{R_p-1}{2}} \equiv -1 \pmod {R_p}$ Proof Let $R_p$ ...
39 views

### The Number of Two-digit Primes Which the Sum of their Digits is 6

Problem: Find the number of two-digit primes which the sum of their digits is six. We had this problem in a mathematic examination. The problem can be solved by testing all two-digit primes, but ...
36 views

### If $p=x^2+y^2$ is a prime number, then $\left( \frac{x+y}{p} \right) = \left( \frac{2}{x+y} \right)$

Let $p=x^2+y^2$ be a prime number. How to prove that $\left( \dfrac{x+y}{p} \right) = \left( \dfrac{2}{x+y} \right)$ (where $\left(\frac ab\right)$ denotes the Jacobi symbol)?
48 views

### An integer sequence defined by recursion

Let's define the following integer sequence. We start with $a_1=3$. Then we define $$a_{n+1}=a_{n}+(a_{n}\,\text{mod}\,p_n)$$ where $p_n$ is the greatest prime (strictly) less than $a_n$, and ...
37 views

### Exponential Power Series where Powers are Prime

I am looking for information in regards to a couple particular functions: 1) $P(x)=\sum_{p\in\mathbb{P}}\frac{x^p}{p!}$ 2) $Q(x)=\sum_{p\not\in\mathbb{P}}\frac{x^p}{p!}$ (assuming $0, 1$ are ...
58 views

### Mersenne numbers fail primality test at 2047 itself. How could we believe Mersennes are primes?

M$_{11}=2047$ is a composite number. How could one, not check the primaility of such a small number and believe that all Mersenne numbers are primes?
43 views

### Finding an upperbound for $\sum_{i=2}^{n}\bigg(\prod_{k=2}^{i}\dfrac{p_k-2}{p_k}\bigg)$

I was wondering whether there exists a known upperbound for: $$f(n)=\sum_{i=2}^{n}\bigg(\prod_{k=2}^{i}\dfrac{p_k-2}{p_k}\bigg)$$ For example: ...
72 views

### How close are we to knowing the rate of convergence to $0$ of $\prod_{p\le x}(1-1/p)^{-1}-e^\gamma\log x$?

This is a question related to an earlier one of mine, which I may answer myself eventually, as I have learnt more about the topic. Despite what one can read on the MathWorld page about Mertens' third ...
42 views

### Finding the $18$th cyclotomic polynomial $\phi_{18}(X))$.

I know that for an $n$th cyclotomic polynomial $\phi_n(X)$ the following equations hold: $x^n-1=\prod_{n_1|n} \phi_{n_1}(X)$ For $n=p$ prime, $\phi_p(X)=X^{p-1}+...+X+1$ So I used the following ...
148 views

### Check if a number is Carmichael

I am trying to implement Modified Miller-Rabin Algorithm by Shyam Narayanan (https://math.mit.edu/research/highschool/primes/materials/2014/Narayanan.pdf). The algorithm demands to check if a number ...
33 views

### Is there a standard way of defining a total order between Gaussian primes?

In the case of $\Bbb N$ and $\Bbb Z$ the gap between two consecutive primes could be defined roughly speaking as the absolute value of the (1-dimensional) distance between those mentioned consecutive ...
263 views

### Primes of form $a^2 + 24b^2$

For a prime number $p \neq 2$, $3$, is it necessarily the case the prime number can be written in the form $a^2 + 24b^2$ if and only if $p \equiv 1 \text{ mod }24$? I think this has to be true based ...
111 views

### Is $every$ prime factor of $\frac{n^{163}-1}{n-1}$ either $163$ or $1\;\text{mod}\;163$?

This was inspired by this question. More generally, given prime $p$ and any integer $n>1$, define, $$F(n) = \frac{n^p-1}{n-1}=n^{p-1}+n^{p-2}+\dots+1$$ Q: Is every prime factor of $F(n)$ ...
58 views

### Largest prime known to ancients

As is well known, Fermat couldn't check the primality of $F_{5} = 2^{2^{5}} + 1$. This raises an interesting question : what was the largest prime number that was known to ancients (particularly ...
45 views

### $\ln(n)$ - Average Length of Prime Gaps

The natural logarithm of $n$ is a good approximation of the prime gap near $n$. On my calculator I enter this as $\ln(n)$. I have read from these pages: ...
37 views

### With which natural value of n, the polynomial will be prime value and why?

So. $P(n) = n^4 + n^2 + 1$ is a polynomial. I calculated that answer is 1. But I don't understand why?
79 views

### Reverse of Chinese Remainder Theorem

For the following: $(102n-51) \not\equiv 2 \pmod {2,3,5,7,11,13,...,\sqrt{102n-51}}$ (That's probably completely incorrect use of symbols, but I mean not equivalent to 2 mod any prime less than ...
138 views

### If $n$ is a positive integer, does $n^3-1$ always have a prime factor that's 1 more than a multiple of 3?

It appears to be true for all $n$ from 1 to 100. Can anyone help me find a proof or a counterexample? If it's true, my guess is that it follows from known classical results, but I'm having trouble ...
48 views

### How many numbers are possible from $a^x b^y c^z$?

How to calculate total nos of possible value made from given numbers. e.g. : $2^2 \cdot 3^1 \cdot 5^1$ . There $2$ , $3$ , $5$ , $2\cdot2$ , $2\cdot3$ , $2\cdot5$ , $3\cdot5$ , $2\cdot2\cdot3$ , ...
16 views

57 views

### Arithmetic Progressions with a Finite Number of Primes

Is there an arithmetic progression that includes {1} that also includes only a finite number of prime numbers? Or will all progressions including {1} have infinite primes?
20 views

### Determine the quadratic character of 293 mod 379…

Determine the quadratic character of 293 mod 379. Did several other problems like this with 3, 5, 60, -1 and 307 all mod 379 but still having a tough time with this problem. I can post up work from ...
Identifying twin primes [1] Any natural number $n : 1<n\leq p_x^2$ where $n$ is not divisible by any prime number less than $p_x$ is a prime number, except when $n$ is one of those prime ...
Please this is very important to me I would be so happy if someone is able to help... :) Let $I$ be a squarefree, natural and even number and $F$ the product of all primes $q$ where $(q-1) \mid I$. ...