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)

5
votes
1answer
234 views

How to find the value of positive integers $a$-through-$h$

If the equation $(x-a)(x-b)(x-c)(x-d)(x-e)(x-f)(x-g) = hx$ has seven positive integer roots, and $a,b,c,d,e,f,g,h$ are positive integers too, how can we find them?
5
votes
2answers
346 views

Sum of squares of sum of squares function $r_2(n)$

Let $r_2(n)$ denote the number of representations of $n$ as a sum of two squares. What is known about the sum of squares of this function, $\sum_{i=1}^n r_2(i)^2$ In particular is anything ...
5
votes
3answers
204 views

Find $a, b, c, d \in \mathbb{Z}$ such that $2^a=3^b5^c+7^d$

Solve $2^a=3^b5^c+7^d$ over the positive integer. I know $a$ is even because: $(-1)^a \equiv2^a = 3^b5^c+7^d \equiv1 \ (mod\ 3)$
5
votes
3answers
459 views

The prime numbers do not satisfies Benford's law

A set of numbers is said to satisfy Benford's law if the leading digit d (d ∈ {1, ..., 9}) occurs with probability, $$ P(d)=\log_{10}(d+1)-\log_{10}d,$$ how do you prove that the prime numbers do ...
5
votes
2answers
1k views

Trying to prove that $p$ prime divides $\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$

So I'm trying to prove that for any natural number $1\leq k<p$, that $p$ prime divides: $$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$$ Writing these choice functions in ...
5
votes
0answers
584 views

Sum of odd prime and odd semiprime as sum of two odd primes?

How to prove that each sum of odd prime and odd semiprime can be written as sum of two odd primes $(p_1+p_2p_3=p_4+p_5)$ ? Since we know that each prime number greater than $3$ is of the form $6k\pm ...
5
votes
1answer
217 views

Silly question about weakly modular functions

This is so far the most naive of my questions. Weakly modular functions of weight $2k$ correspond to $k$-forms on $X(1)$, right? But $X(1)$ is a curve. So shouldn't there not be any $k$-forms for ...
5
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 ...
5
votes
3answers
1k views

Existence of solutions to diophantine quadratic form

Is there a general result about the existence of (non-trivial) solutions of the diophantine equation: $$Ax^2 + By^2 = Cz^2$$ for A,B,C known positive integers, pair-wise relatively prime? What if ...
5
votes
1answer
340 views

Is every finite separable extension of a strictly henselian DVR totally ramified?

Let $R$ be a discrete valuation ring with field of fraction $K$ and residue field $k$ and let $K'$ be a finite and separable extension of $K$. If $R$ is henselian ("Hensel's lemma holds", e.g. if ...
5
votes
1answer
751 views

Efficiently calculating the logarithmic integral with complex argument

My number theory library of choice doesn't implement the logarithmic integral for complex values. I thought that I might take a crack at coding it, but I thought I'd ask here first for algorithmic ...
5
votes
2answers
391 views

Algorithms to compute the class number

Let the class number $h(d)$ denote the number of distinct binary quadratic forms with discriminant $d < 0$. Is there a better algorithm for $h$ than brute force? To be precise, by brute force I ...
4
votes
1answer
79 views

Prime numbers are related by $q=2p+1$

Let primes $p$ and $q$ be related by $q=2p+1$. Prove that there is a positive multiple of $q$ for which the sum of its digits does not exceed $3$. My work so far: $p,q -$ primes and $q=2p+1 ...
4
votes
1answer
66 views

Show that there exist no $a, b, c \in \mathbb Z^+$ such that $a^3 + 2b^3 = 4c^3$

Find all positive integer solutions of $a^3 + 2b^3 = 4c^3$. Proof: There don't exist any integer solutions for the give equation. Proof by the Well Ordering Principle. Let $d$ be the set of all ...
4
votes
4answers
187 views

Remainder when ${45^{17}}^{17}$ is divided by 204

Find the remainder when ${45^{17^{17}}}$ is divided by 204 I tried using congruence modulo. But I am not able to express it in the form of $a\equiv b\pmod{204}$. $204=2^2\cdot 3\cdot 17$
4
votes
1answer
179 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
243 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
184 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
107 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
121 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
176 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
321 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
899 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
776 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
722 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
691 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
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
260 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
45 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 ...