Questions on more advanced topics of number theory, such as quadratic residues, primitive roots, prime numbers, non-linear Diophantine equations, etc. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.

learn more… | top users | synonyms (1)

4
votes
1answer
177 views

Can a conic over $\mathbb{Q}$ with no $\mathbb{Q}$-points have a point of degree 3?

Let $C$ be the conic in $\mathbb{P}^2$ given by $ax^2 + by^2 + cz^2 = 0$ with $a,b,c\in\mathbb{Q}$. (every genus 0 curve over $\mathbb{Q}$ can be given this way right?) Suppose $C$ has no rational ...
4
votes
1answer
87 views

Does Euler's $\phi$ function have the same value in arbitrarily large subsets of $\mathbb{N}$?

As my most recent question still does not have any answers and it appears to be a difficult problem, I propose the following problem (that seems easier), but which I still could not manage to solve: ...
4
votes
1answer
109 views

Prove that powers of any fixed prime $p$ contain arbitrarily many consecutive equal digits.

Prove that powers of any fixed prime $p$ contain arbitrarily many consecutive equal digits. It is an intuitive re-statement of Baltic Way 2012 (I think there are shortlists in Baltic Way every ...
4
votes
1answer
69 views

How many values of $k$ satisfy $\left (\frac{k}{p}\right )=\left (\frac{k+1}{p}\right)=1$ where p is a odd prime?

The values of $k$ must be between $1$ and $p-1$ this means : $$k\in\left\{1,2,\cdots,p-1\right\}$$ The question: Given an odd prime $p$ What is the number of elements ...
4
votes
2answers
240 views

How to solve $(2x^2-1)^2=2y^2 - 1$ in positive integers?

I encountered this question (posed by Fermat) in a letter from Fermat to Carcavi and was wondering what would be the best elementary way to solve it. Solve in positive integers$$(2x^2-1)^2=2y^2 - ...
4
votes
4answers
179 views

What is the smallest positive integer of the form $30x+6y+10z$? [closed]

I am trying to find the smallest positive integer of the form $30x+6y+10z$, where $(x,y,z)\in\mathbb{Z}$ However, I do not know where to start. Hints or answers are welcome. Thanks!
4
votes
0answers
106 views

More on primes $p=u^2+27v^2$ and roots of unity

Given, $$p=u^2+27v^2=3m+1\tag1$$ and the cubic, $$x^3+x^2-mx+N=0\tag2$$ with its constant expressed in terms of $(1)$ as, $$N = \frac{1}{27}(1-3p\pm2pu)\tag3$$ and the sign $\pm u$ chosen ...
4
votes
1answer
166 views

Additive function $f: \mathbb{Z}^\infty \rightarrow \mathbb{Z}$ is zero everywhere.

Let $f: \mathbb{Z}^\infty \rightarrow \mathbb{Z}$ be an additive function ($f(x+y)=f(x)+f(y)$ for every $x,y \in \mathbb{Z}^\infty$). In addition for every $x=(0,\dots, 0,1,0, \dots)$ we have ...
4
votes
1answer
112 views

The Island in the Miracle Sea. (Christmas edition)

To all of you who love math like me, I have this puzzling riddle that I hope you find interesting : On Christmas Eve just after midnight, Santa was riding his sleigh over the Miracle Sea when ...
4
votes
1answer
110 views

$p^3 + 2$ is prime if $p$ and $p^2 + 2$ are prime?

I'm self-learning number theory. I want to prove the following statement: $$p \text{ is prime } \land \text{ }p^2 + 2 \text{ is prime } \implies p^3 + 2 \text{ is prime }$$ I failed to do so, and I ...
4
votes
3answers
101 views

What is known about $x^m + y^m = z^n$ over $\mathbb{N}$ when $m,n \geq 2$ and $m \neq n$?

So Fermat's Last Theorem resolves the question of positive integer solutions to $x^m + y^m = z^n$ when $m = n \geq 3$. But what about if $m \neq n$ and $m,n \geq 2$? Is anything general known about ...
4
votes
2answers
136 views

The Conjecture That There Is Always a Prime Between $n$ and $n+C\log^2n$

Let $n$ be 113. Use $n+C\log^2n$ to find the next consecutive prime or at least approximately how far away it is. Will you show me how to work this out step by step to show me how to use this formula? ...
4
votes
1answer
108 views

Asymptotics on the largest prime for which $x^n+1\equiv y^n$ has no nonzero solution

It $\let\epsilon\varepsilon\let\leq\leqslant\let\geq\geqslant$is a well known result that for every $n\in\mathbb N$, $x^n+1\equiv y^n\pmod p$ is non-trivially solvable for sufficiently large primes ...
4
votes
1answer
111 views

Limit of differences of truncated series and integrals give Euler-gamma, zeta and logs. Why?

In the MSE-question in a comment to an naswer Michael Hardy brought up the following well known limit- expression for the Euler-gamma $$ \lim_{n \to \infty} \left(\sum_{k=1}^n \frac 1k\right) - ...
4
votes
2answers
6k views

Prove that every odd prime number can be written as a difference of two squares.

Prove that every odd prime number can be written as a difference of two squares. Prove also that this presentation is unique. Is such presentation possible if p is just an odd natural number? Can 2 ...
4
votes
0answers
118 views

Number of Solutions to a Diophantine Equation

I am asked the following: Show that the number of integer solutions to $y^p=x^2+2$ for any odd prime $p$ is at most $p-1$. I checked that for $y^p=x^2+2$, the same method for $y^3=x^2+2$ works ...
4
votes
3answers
175 views

A game with two dice

Imagine a game with two dice, played by two people and a referee. The referee rolls the first die and the number will determine the number of times that the second die will be rolled. The two players ...
4
votes
2answers
158 views

Conjecture involving semi-prime numbers of the form $2^{x}-1$

Let $x$ be a positive integer such that $(2^{x}-1)=pq$ , where $p$ and $q$ are prime numbers. I want to show that either $p^{2} \bmod x \equiv 1$ or $q^{2} \bmod x \equiv 1$ (or both of course). Is ...
4
votes
2answers
320 views

Calculating $a^n\pmod m$ in the general case

It is well known, that $$a^{\phi(m)}\equiv1\pmod m ,$$ if $\gcd(a,m)=1.$ So, $a^n\pmod m$ can be calculated by reducing n modulo $\phi(m)$. But, for the tetration modulo $m$ $$a \uparrow ...
4
votes
4answers
883 views

How can we compute the multiplicative partition function

Please how can we compute the multiplicative partition function. For example $24$, has precisely $6$ valid factorizations: $2\cdot2\cdot2\cdot3$, $2\cdot2\cdot6$, $2\cdot3\cdot4$, $2\cdot12$, ...
4
votes
3answers
19k views

How to find all perfect squares in a given range of numbers?

I need to write a program that finds all perfect squares between two given numbers a and b such that the range can also be a = 1 and b = 10^15 what is the best way I can do this, how do I list down ...
4
votes
1answer
177 views

Solve in integers $ (y^3+xy-1)(x^2+x-y)=(x^3-xy+1)(y^2+x-y)$

Solve in integers: $$ (y^3+xy-1)(x^2+x-y)=(x^3-xy+1)(y^2+x-y)$$ My idea: $$\Longleftrightarrow (y^3+xy-1)(x^2+x-y)-(x^3-xy+1)(y^2+x-y)=0$$ $$\Longleftrightarrow ...
4
votes
1answer
759 views

Non-integer bases and irrationality

I read somewhere: When it comes to properties like prime, irrational, rational, divisible by 2, etc., nothing changes when you change base. But I'm not sure about the rational/irrational one. ...
4
votes
0answers
268 views

Period of decimal for $1/n$, odd part of $n+1$, and primes.

Let $n$ be a nature number is coprime to $10$,such that the period of the decimal expansion of $1/n$ is a divisor of $n-1$, and let $c$ be the "cycle length of $n$" (defined below). If $n-1=2^xc$ ...
4
votes
2answers
277 views

Elements of finite order in the group of arithmetic functions under Dirichlet convolution.

Let $(G, ∗)$ be the group of arithmetic functions $f : N \to C$ that satisfy $f (1)\neq 0$, with group operation given by the Dirichlet product $∗$. The identity function $I$ is the identity element ...
4
votes
2answers
714 views

Bounding the prime counting function

How can I get inequalities that bound the prime counting function if I have the following inequalities for some functions $f(x)$ and $g(x)$: $$ g(x)<\psi(x)<f(x), $$ where $\psi(x)$ is second ...
4
votes
1answer
126 views

A high-powered explanation for $\exp U(n)=2\iff n\mid24$?

In What's so special about the divisors of $24$? it is noted that the exponent of the group of units modulo $n$, that is the highest order of an element of $U(n):=(\Bbb Z/n\Bbb Z)^\times$, is ...
4
votes
2answers
345 views

combinatorial question (sum of numbers)

I am having trouble with some combinatorial question. Its not my field and the question is difficult for me. Any help will be appreciate. Let $m_1,..., m_{{M}}$ be numbers such that $m_i \in \{0, ...
4
votes
2answers
360 views

Are there infinitely many primes of the form $6^{2n}+1$ or only finitely many?

Does anyone know whether there are only finitely many of primes of the form $6^{2n}+1$, where $n$ zero or any natural number?
4
votes
2answers
686 views

What is importance of the Bunyakovsky conjecture?

Bunuyakovsky conjecture states that: An irreducible polynomial $f(x)$ of degree two or higher with integer coefficients and property that $\gcd(f(1),f(2),......)=1$ generates for natural ...
4
votes
1answer
2k views

Hardy Ramanujan Asymptotic Formula for the Partition Number

I am needing to use the asymptotic formula for the partition number, $p(n)$ (see here for details about partitions). The asymptotic formula always seems to be written as, $ p(n) \sim ...
4
votes
2answers
239 views

RSA: Creating a key of desired length

Thanks and with respect to the users of this site, I've succeeded in creating an Encryption/Decryption procedure for the RSA algorithm. I also implemented a Miller-Rabin probabilistic primality test. ...
4
votes
1answer
159 views

Are limits on exponents in moduli possible?

Suppose I show that: $$x^{f(z)/g(z)} = y \pmod{4}$$ is impossible for some given positive integers $x$ and $y$, where, \begin{align*} f(z) &= \phi(4) k_1(z) + 1 \\ &= 2 k_1(z) + 1\\ g(z) ...
4
votes
1answer
258 views

Proving $P( n) =n^{\phi(n)} \prod\limits_{d \mid n} \biggl(\frac{d!}{d^d} \biggr)^{\mu(n/d)}$

Actually, i had posted this long ago in MO, and i didn't get a reply to this question as it was unfit. Now, this is an exercise, in some textbook ( i think Apostol) and i would be happy if i can ...
3
votes
1answer
44 views

Show that a Sophie Germain prime $p$ is of the form $6k - 1$ for $p > 3$

A Sophie Germain prime is a prime $p$ such that $2p + 1$ is also prime. According to a comment in OEIS A023212 (https://oeis.org/A023212), such a prime $p$ is of the form $6k - 1$ for $p > 3$. ...
3
votes
1answer
72 views

Rational points on $y^2 = 12x^3 - 3$.

Prove by elementary arguments that the only rational point on the title curve is $(x, y) =(1,\pm 3)$. My attempt was the standard approach of factoring $(y+i\sqrt 3)(y - i\sqrt 3) = 12x^3$, but it ...
3
votes
1answer
48 views

Does $\sum_{n=1}^\infty \frac{1}{p_ng_n}$ diverge?

I know of Euler's proof that the sum of the reciprocals of the primes diverges. But what if we multiply the primes by it's following prime gap. In other words, is $$\sum_{n=1}^\infty \frac{1}{p_ng_n} ...
3
votes
1answer
83 views

Can different tetrations have the same value?

Suppose, we have two numbers $a\uparrow \uparrow b$ and $c\uparrow \uparrow d$. To avoid trivial cases, suppose $a,b,c,d>2$ and $(a,b)\ne (c,d)$. Is there a quartupel $(a,b,c,d)$ with ...
3
votes
1answer
32 views

Non-additive asymptotic upper density: $\mathsf{d}^\star(A\cup B) \neq \mathsf{d}^\star(A)+\mathsf{d}^\star(B)$

Let $\mathsf{d}^\star$ be the asymptotic upper density on $\mathbf{N}$, that is, for each $X\subseteq \mathbf{N}$ we have $\mathsf{d}^\star(X)=\limsup_n |X\cap [1,n]|/n$. Then, is it possible to ...
3
votes
1answer
87 views

Infinite number of primes of the form $2^x \cdot 3^y + 1$?

Are there an infinite number of primes of the form $2^x \cdot 3^y + 1$? I really have no idea where to start with this. I thought of it because it would imply an affirmative answer to this recent ...
3
votes
3answers
61 views

Split 16 Consecutive Integers into Two Subsets of 8 Integers

Show that any given set of sixteen consecutive integers {$x+1,x+2,\ldots,x+16$} can be divided into two eight element subsets with the properties that they have the same sum, the sums of the squares ...
3
votes
1answer
61 views

Pell's equation and representation elements of $\mathbb Z_p$.

We defined the function $f:\mathbb Z_p \times \mathbb Z_p \rightarrow \mathbb Z_p$ such that $f(x,y)=x^2-cy^2$ and $c\not\equiv 0\pmod{p}$. Is it true that $f$ is onto?
3
votes
3answers
196 views

Divisibility of polynomial

Prove that: $(x^2+x+1) \mid (x^{6n+2}+x^{3n+1}+1) $ and $(x^2+x+1) \mid (x^{6n+4}+x^{3n+2}+1) $. I saw proof in book with third roots of unity but i didn't understand it, so i want to see ...
3
votes
1answer
212 views

Number theory / Group theory: consecutive integers divisible by at least n prime numbers

Claim: There exist 15,251 successive positive integers $a_1, a_2\dots,a_{15251}$ such that each $a_i$ where ($1\le i\le 15251$) is divisible by at least 251 different prime numbers Is there a neat ...
3
votes
1answer
74 views

How find this such that $n\mid 3m+1$ and $ m\mid n^2+3$

Find all pairs $(m,n)$ of positive odd integers,such that $$n\mid 3m+1$$ and $$ m\mid n^2+3$$ My idea: since $$3m+1=an,p\in N^{+}$$ $$n^2+3=bm$$ I fell this try is not usefull,so I can't Continue ...
3
votes
2answers
298 views

Proof of $ \phi(n) = \sum_{n|d} \mu(d) \cdot\frac nd $

I'd like to prove $\phi(m)=\sum_{m|d}\mu(d)\cdot\frac md$. If I'm right then we have for euler-phi $\phi(n) = \sum_{m \leq n,\gcd(m,n)=1} 1$ Which means: as long as $m$ is less or equal than $n$ ...
3
votes
1answer
448 views

Cubic diophantine equation

How can I solve the equation $x^3+x-1=y^2$ in positive integers? I know this equation defines an elliptic curve but this seems to be a non-elementary way to solve the question. Is there a more ...
3
votes
1answer
118 views

Algorithm to find solutions $(p,x,y)$ for the equation $p=x^2 + ny^2$.

As the classical book of David Cox argues, Assume the conditions are satisfied and $p$ can be represented as $x^2 + ny^2$. What would be a way to find solutions $(p,x,y)$ efficiently? Ideally, one ...
3
votes
2answers
276 views

A cubic Diophantine equation in two variables

Find all POSITIVE integer solutions to the following cubic equation: $x^3+2x+1=y^2$. Notice how the left side of the equation resembles $x^2+2x+1=(x+1)^2$. The only solutions I've been able to find ...
3
votes
3answers
492 views

sets with no asymptotical density over $\mathbb N$

Let's consider the Natural density on $\mathbb N$ defined by: Take $ A\subset \mathbb N$; define the sequence $x_n= \dfrac{|A\cap[1,n]|}{n}$, and then if $\lim\limits_{n\to\infty} x_n$ exists, ...