0
votes
0answers
11 views

Program for Handling Huge Primes

I am trying to run a program with really large primes (around the $10^{20}$th prime), but Mathematica seems to only be able to handle around the first $10^{12}$ primes. Is there any software that can ...
0
votes
0answers
20 views

If $k\le n$ and $k$ is relatively prime to $n$, there exists a prime $p$ such that $p \equiv k \mod n$.

I need to use this result in a step of a proof, but I am for some reason unable to justify it. It seems to be true, after trying some examples, but I am not sure why. If $1 \le k\le n$ and $k$ is ...
4
votes
1answer
39 views

Show that $3^n-2^n\cdot 5$ is composite for infinitely many $n$

I came across this problem: Show that $3^n-2^n\cdot 5$ is composite for infinitely many $n$ and do not know how to solve it. I only know that it is true for $n=7$, since then $1547=17\cdot 91$.
1
vote
1answer
21 views

Is a Mersenne prime always of the form $4n + 3$?

Is a Mersenne prime always of the form $4n + 3$? Examples: $M_3 = 7 = 4 \times 1 + 3$ $M_5 = 31 = 4 \times 7 + 3$ $M_7 = 127 = 4 \times 31 + 3$ $M_{13} = 8191 = 4 \times 2047 + 3$ ...
1
vote
1answer
123 views

Consider the number $n= 2^{10^{33}} +1$ [on hold]

Consider the number $$n= 2^{10^{33}}+1$$ Suppose that it is known that none of the numbers $1 < k < 10^{6}$ divide $n$. Does it follow that n is a prime number? I know that the answer is a ...
2
votes
1answer
27 views

ON types of squarefree numbers and comparing their amounts < a given integer N.

Let an m-prime be a square-free number with m prime divisors. Also let the number of t-primes < N be represented as #(t-prime){N} (t and N being positive elements of integers). Is the following ...
3
votes
0answers
70 views

diophantine equation $ |x^2-py^2|=\frac{p-1}{2} $

Prime $p\equiv3\pmod4$, then diophantine equation $$ |x^2-py^2|=\frac{p-1}{2} $$ has a solution in integers obviuosly, en, $x^2-py^2=-1$ has no solution in integers. Thanks a lot!
1
vote
0answers
33 views

About primes and counting them. [on hold]

Are there bounds to the prime counting function that do not involve logarithms? Considering the best bounds use logarithms why is the natural logarithm so closely related to the prime counting ...
0
votes
1answer
47 views

infinite primes $p\equiv1\pmod n$ without cyclotomic polynomial

Without cyclotomic polynomial, is there an elementary proof of the following: for each integer $n>1$, there are infinitely many primes $p$ such that $p\equiv1\pmod n$ ? please don't refer to ...
2
votes
1answer
33 views

Concerning types of square-free numbers and comparing sizes of their subsets.

Call a square-free a 2-prime if it has exactly two prime divisors. Call a square-free a 3-prime if it has exactly three prime divisors,etc. Does there exist an integer N > 230 such that the number of ...
1
vote
2answers
42 views

Concerning types of square-free numbers.

Call a square-free number a 3-prime if it is the product of three primes. Similarly for 2-primes, 4-primes , 5-primes, etc. Are there two consecutive 3-primes with no 2-prime between them?Are there ...
3
votes
2answers
84 views

elementary proof that infinite primes quadratic residue modulo $p$

$p \gt 2$ is a prime, then there are infinite primes $q$ such that $q$ is a quadratic residue modulo $p$. With Dirichlet's theorem on arithmetic progressions, the problem is easy! How about ...
4
votes
1answer
99 views

Primality of the number of obtained by concatenating the n consecutive digits

Let $f_n$ be the number obtained by concatenating the first $n$ numbers (in base 10). For example $f_1 = 1, f_3 = 123$ and $f_{13} = 12345678910111213.$ Now if $n$ is even or divisible by $5$ then ...
1
vote
1answer
38 views

Confused by a step in a proof that $a^x - b^y = c$ has at most two solutions in positive integers $x,y$

The theorem is Theorem 1.1 from Michael A. Bennett in his "On Some Exponential Equations of S.S. Pillai". Here is the statement of the theorem: Theorem 1.1. If $a,b,c$ are nonzero integers with $a,b ...
0
votes
1answer
16 views

Need help in understanding $ord_p{a}$ as used in Theorem 1.1 from “On Some Exponential Equations Of S. S. Pillai”

I have a question about very early argument in the proof of Thereom 1.1. Theorem 1.1 of On Some Exponential Equations of S.S. Pillai states that if $a,b,c$ are nonzero integers with $a,b \ge 2$, then ...
1
vote
1answer
53 views

Solve for $p^a + 1 = 2\cdot q^b$ where $p,q$ are odd primes and $a,b \ge 2$

Now, clearly, $7^2 + 1 = 2\cdot5^2$. Is this the only solution? How would I prove this? Or if it is not the only solution, what would be the method to find other solutions? I'm not clear on how to ...
0
votes
0answers
11 views

If $p^a \equiv -1 \pmod {q^b}$, is there anything that we can say about $a$ if $p,q$ are odd primes and $a,b > 1$

If $p^a \equiv 1 \pmod {q^b}$, then, from Carmichael's Theorem, we know that: $a = u\varphi(q^b) = u(q-1)(q^{b-1})$ where $u \ge 1$ Can we say anything similar if $p^a \equiv -1 \pmod {q^b}$
3
votes
2answers
50 views

Proving that if $a,b > 1$, then $5^a - 3^b=16$ has only one solution with $a=2$ and $b=2$

This may be one of those problems that is easy to state but very hard to prove. I don't know. I have tried to show that there is only one solution but I have not made much progress. Here's what I ...
1
vote
1answer
47 views

Subset of prime numbers

Given a subset of prime numbers say $A$. It is given that for $p,q\in A$ we also must have $(pq+4)\in A$ . Show that $A=\phi$ My work so far: It is obvious that $2,3\notin A$ . because all the ...
1
vote
1answer
58 views

Does a solution exist where $p,q$ are odd primes and $p^a - q^b = p^c - q^d$ where $a > c > 1$ and $b > d > 1$

From my thinking so far, there is no solution. Is this an open question or is the answer well known? Here's my reasoning about this issue: If a solution exists, then: $$p^c(p^{a-c} - 1) = ...
0
votes
0answers
31 views

Find $a,b,c \ge 2$ and $p,q$ odd primes where $p^a - 1 = c*q^b$

I've been recently thinking about finding primes $p,q$ where the power of one divides the power of the other when subtracted by $1$. For example, if we remove the requirement that $p,q$ be odd ...
0
votes
0answers
23 views

Miller-Rabin primality test and testing one

I'm learning about Miller-Rabin primality test but in all the problems I see in the notes of a person I got them from, I see that even if he expressed the number as $2^1 \cdot something$, he still ...
3
votes
2answers
41 views

Proof for the existence of primes not equal to $ap_\alpha +bp_\beta$ etc?

Is there a general proof to show that there exists prime numbers larger than $min(p_\alpha,p_\beta)$that are not equal to $ap_\alpha +bp_\beta$, given $p_\alpha,p_\beta\in\mathbb{P}-\left\{2\right\}$ ...
2
votes
0answers
38 views

My first proof employing strong induction / complete induction (very simple number theory). Please mark/grade.

What do you think about my first proof employing strong induction? What mark/grade would you give me? Theorem Every natural number greater than 1 is a product of one or more primes. Proof First, ...
1
vote
0answers
43 views

Show that $16$ is a perfect $8$th power modulo $p$ for any prime number $p$ [duplicate]

Show that $16$ is a $8th$ power $\mod{}$ $p$ for any prime number $p$. I have no idea how to approach this. I tried, $$a^8\equiv16\pmod{p}$$ $$(a^4+4)(a^4-4)\equiv 0 \pmod{p}$$ $$a^4 \equiv ...
1
vote
3answers
37 views

Prove that for all $a\in \mathbb{Z}$ and all primes $p$, $p^2$ does not divide $a^2-p$

What would be a method to start, or some can prove useful theorem for this problem Prove that for all $a\in \mathbb{Z}$ and all primes $p$, $p^2$ does not divide $a^2-p$
2
votes
1answer
42 views

How to do partial summation?

I don't understand the following step in a proof: gcd(k,l)=1. Then we have the following formula (p is a prime number): $\sum_{p\leq x, p\equiv l( k)}{\frac{log^2(p)}{p}}\leq ...
0
votes
0answers
40 views

Mathematical function alike to primes

Note: I'm currently in a low level algebra class and have very little knowledge of some of the more complex mathematical concepts. That being said, I can probably figure out anything I don't know ...
0
votes
0answers
48 views

Fermat's Little Theorem not useful as $p\rightarrow\infty$

I'm having trouble with some questions of which Fermat's little theorem doesn't seem to simplify enough. For questions such as What is $10^{41} \text{mod}\;49$? I get stuck. Since ...
2
votes
1answer
54 views

About the multiplicative order of $2$ modulo a prime

Is this true, that for all integer $n>0$, but $n=1$ and $n=6$, there exists a prime $p$ such that $n=ord_p(2)$, where $ord_p(2)$ is the multiplicative order of $2$ modulo $p$? If not, what is the ...
4
votes
1answer
59 views

Question about the number of primes greater than $3$ in a sequence of consecutive integers.

I recently noticed that for any $x > 16$, it follows that there are at least $2$ integers in the any sequence of 3 consecutive integers that are divisible by a prime greater than $3$. For example, ...
7
votes
3answers
184 views

If a prime can be expressed as sum of square of two integers, then prove that the representation is unique.

If a prime can be expressed as sum of two squares, then prove that the representation is unique. My attempt: If $a^2+b^2=p$, then it is obvious that $a,b$ of different parity. Now, I assume the ...
0
votes
2answers
68 views

Primality of $2^q\pm2^{(q+1)/2}+1$ when $q$ is an odd integer

It can be quite easily shown that $5$ is a divisor of $2^q+2^{(q+1)/2}+1$ iff ($q=8k+1$ or $q=8k+7$) and that $5$ is a divisor of $2^q-2^{(q+1)/2}+1$ iff ($q=8k+3$ or $q=8k+5$). Now, it seems that ...
5
votes
1answer
54 views

Sum of a certain series related to the primes

It is well known that $$\sum_{n > 0}\frac{1}{n}$$ diverges, but $$\sum_{n > 0}\frac{1}{n^2} = \frac{\pi^2}{6}$$ converges. Similarly, $$\sum_{p}\frac{1}{p}$$ diverges, but $$\sum_{p} ...
0
votes
1answer
94 views

Prove that $2^x \cdot 3^y - 5^z \cdot 7^w = 1$ has no solutions

Prove that $2^x \cdot 3^y - 5^z \cdot 7^w = 1$ has no solutions in $\mathbb{Z}^+$, if $y\ge 3$.
0
votes
0answers
42 views

It has been conjectured that there are infinitely many primes in the form $n^2-2$. Exhibit five such primes.

It has been conjectured that there are infinitely many primes in the form $n^2-2$. Exhibit five such primes. I'm so confused what the problem is asking. Do I just need to find examples or an ...
4
votes
2answers
100 views

Primes $p$ such that $p^2$ divides $x^2 + y^2 + 1$

Call a prime $p$ awesome if there exist positive integers $x$ and $y$ such that $p^2$ divides $x^2+y^2+1$. Observation: $2$ is not awesome, because $x^2+y^2+1\not\equiv 0$ (mod $4$). But $3$ is ...
1
vote
0answers
52 views

Primality of $P_{q,j}=(2^{q^{j+1}}-1)/(2^{q^j}-1)$ , when $q$ is prime, $j\ge0$?

Let $P_{q,j}=(2^{q^{j+1}}-1)/(2^{q^j}-1)$ , $q$ prime and $j\ge0$. $P_{2,j}$ is a Fermat number, $P_{q,0}$ is a Mersenne number. Apart from Fermat primes and Mersenne primes, and apart from ...
12
votes
4answers
934 views

Why is Euler's Totient function always even?

I want to prove why $\phi(n)$ is even for $n>3$. So far I am attempting to split this into 2 cases. Case 1: $n$ is a power of $2$. Hence $n=2^k$. So $\phi(n)=2^k-2^{k-1}$. Clearly that will ...
1
vote
1answer
36 views

Divisibility problem with product of two primes

Be $n=pq$ a natural number product of two different primes $p,q$. Prove, that on the set $\{1.2,2.3,...,n(n+1)\}$ there are exactly 4 numbers divisible by $n$.
4
votes
1answer
125 views

Can the twin prime conjecture be solved in this way?

After some research, I have discovered that proving the statement; There exist an infinite number of positive integers K such that; $K \neq 6ab \pm a \pm b$ and $K \neq 6ab \mp a \pm b$ is ...
4
votes
1answer
59 views

Prime number that are recursively made up of other prime number — what is this called

I've noticed that some prime number are composed entirely of other prime numbers for example -- some have parents on the left hand side (all the numbers below are prime): ...
2
votes
1answer
69 views

How to disprove the statement…

Statement: There are an infinite number of primes of the form 4N+1 and a finite number of primes of the form 4N-1. How would you disprove this ?
6
votes
1answer
90 views

How to compute the mean average exponent of the naturals? What is the limit for large numbers?

With a friend I was trying to get an understanding for why the expected gap between primes is logarithmic. With that motivation I tried to express the average exponent of numbers. By average ...
4
votes
1answer
63 views

Who generates the prime numbers for encryption?

I was talking to a friend of mine yesterday about encryption. I was explaining RSA and how prime numbers are used - the product $N = pq$ is known to the public and used to encrypt, but to decrypt you ...
1
vote
1answer
61 views

Primes and infinite primes of the form

can you give the validity or proof of the following statements of my observations on Primes? $(1)$ For a positive integer $k$, there exists infinitely many primes of the form $29 + 72k$. $(2)$ If the ...
5
votes
1answer
292 views

A club for some special prime numbers: new members welcome

Given an integer $i$, find an integer $n$ ( $2^{j-1}\le n <2^j$), and a prime divisor $p$ of $M_n=2^n-1$, so that $v= j+i$; where $p$ is written as $k2^v+1$, $k$ odd. In other words, $j$ is such ...
1
vote
1answer
38 views

Co-primality of coefficients of coprime integers

Given that $a,b$ are co-prime, we have infinitely many solutions for $x,y$ to the equation $$ax+by=c.$$ Furthermore, solutions have the form: $x=ca^{-1}+tb,y=cb^{-1}-ta$. Given that $c$ ...
0
votes
1answer
86 views

A question about prime divisors of Mersenne number $M_n= 2^n-1$ when $n$ is odd

Is this true that a prime divisor of a Mersenne number $M_n = 2^n-1$ when $n$ is odd, cannot be a Proth prime (i.e. a prime number of the form $2^mk+1$, where $k<2^m$)? If yes, how is it ...
2
votes
3answers
86 views

Determine the largest 3-digit prime factor of ${2000 \choose 1000}$

Determine the largest 3-digit prime factor of ${2000 \choose 1000}$. I could not approach the problem at all. I have no idea how to try the problem. Please help.