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)

0
votes
0answers
13 views

Truncating Legendre's Formula

Let $p_n$ denote the $n^{th}$ prime. Legendre's Formula, $\phi(x,a)$, counts the number of integers less than or equal to $x$ that are not divisible by the first $a$ primes. Define therefore ...
1
vote
2answers
63 views

$X^4 - 4Y^4 = -Z^2$ has no solutions in non zero integers

I am trying to prove that $X^4 - 4Y^4 = -Z^2$ has no solutions in non zero integers. I know there are similar questions on MS, but that minus signs before the $Z$ gives me a hard time. For the ...
2
votes
1answer
81 views

Solve in integers $b^{11}-1=a^{2016}+a^{2015}+\dots+1$

Find all integers $(a,b)$ satisfying $$b^{11}-1=a^{2016}+a^{2015}+\dots+1.$$ Obviously, we can get the factorisation $(b-1)(b^{10}+\dots+1)=a^{2016}+a^{2015}+\dots+1$, but I'm not sure how to ...
0
votes
1answer
80 views

Any counter example for this claim?

I would like to proof or disproof this claim ,but i don't have enough information about divisor function structure . Claim : for any positive integer $x, y ,n $ such that :$x\neq y$ and ...
3
votes
1answer
71 views

Asymptotic relation for the following series?

Questions Is the asymptotic relationship correct? How do I determine $c_1$ and $\kappa$? As, $|s| \to 0$ $$ \sum_{r=1}^\infty s^r \ln(r) \sim c_1 \sqrt{s} + (\kappa - 1 + \frac{\ln(2 \pi)}{2} ...
3
votes
1answer
124 views

Who knows further prime factors of $3^{3^3}+4^{4^4}=3^{27}+4^{256}\ $?

The partial prime factorization of $$3^{3^3}+4^{4^4}=3^{27}+4^{256}$$ is $$43\times 691\times C150$$ , where C150 = ...
2
votes
0answers
52 views

infinitude of primes with the form $n^2+1$ [closed]

Is there any progress in proving the infinitude of prime numbers of the form $n^2+1$ ?
0
votes
2answers
31 views

Modular Linear Equations

I am revising for one of my Computer Science exams, and a repetitive question keeps coming up; however it's very maths based. And I suck at mathematics. Question $3)$ Consider the following two ...
1
vote
0answers
39 views

Elementary divisibility problem.

I was doing an elementary number theory exercise in a certain text, and i came across this problem: Is there an even integer $n$ such that $1^n + 2^n + \cdots +m^n$ divides $(m+1)^{n}(m^n - 2^n)$, ...
1
vote
0answers
29 views

On sets with positive density.

I'm a prospective undergraduate student who is deeply passionate about number theory and i just came across the interesting concept of density of sets. My question: If the set of integers $x$ such ...
1
vote
2answers
67 views

Largest Mersenne composites with prime exponent?

I understand that it is an open problem whether there are an infinite number of composite numbers of the form $2^p-1$ with $p$ prime. Is it possible to find examples of such numbers that are much ...
3
votes
1answer
45 views

Is there an upper bound on the growth rate of analytic functions?

This problem comes from a solution tactic used in Is there a rational surjection $\Bbb N\to\Bbb Q$?, where I discovered that there is an analytic function $f(z)$ that takes the values $f(n)=a_n$ for ...
4
votes
2answers
36 views

Understanding of Proof of Wilson's Theorem

In my algebraic structures textbook there is a proof for the theorem if $p$ is a prime then $(p-1)!\equiv -1\pmod p\ $. Proof: Since p is prime, each element $1,2,3...(p-1)$ in $\Bbb Z_p $ has an ...
0
votes
0answers
21 views

Infiniate number of ways to algebraicly describe pythagorean triplets from a seed triplet.

For any given triplet $x^2+y^2=z^2$ example 3,4,5 there exists another triplet $x_2=x+2y+2z$ $y_2=2x+y+2z$ $z_2=2x+2y+3z$ $x_2^2+y_2^2=z_2^2$ example 21,20,29 and another triplet $x_3= -x+2y+2z$ ...
1
vote
1answer
28 views

Defining Primes in Non-standard Models of Peano Arithmetic

I was recently reading a post basically discussing an "intuition" that Goldbach's Conjecture may be a statement which is undecidable (the post does not specify which axiomatic system the statement is ...
0
votes
1answer
22 views

What's the formulation of N-point radix-N for NTT

We can write the formulation for the buttlerfly function applied in FFT as \begin{align*}y_0 &= x_0 + x_1,\\ y_1 &= x_0 - x_1. \end{align*} As seen here. For FFT (Fast Fourier Transform) we ...
4
votes
0answers
65 views

Proving the decomposition $N = a^a b^b$ is unique or not

Suppose $a,b,c,d$ be natural numbers. If $a \ge b > 0$, $c \ge d > 0$, $a^a b^b = c^c d^d$, then $a = c$ and $b = d$. For example, can we find another decomposition of $N$ when $N = 8^8 4^4$ ? ...
2
votes
0answers
97 views

Number-theoretic asymptotic looks false but is true?

Question Let $p_r$ be the $r'th$ prime. Is it true that, $$\sum_{r=1}^\infty s^r \ln(p_r) \sim \frac{s}{(1-s)} $$ I know this looks bizarre but kindly consider the argument below. I'm also ...
0
votes
2answers
42 views

Sets of positive integers closed under lcm/gcd?

Is there an exact, workable description of sets of positive integers closed under the lcm or gcd operations? In other words, a set of ideals of Z which is closed under intersections or sums. My ...
6
votes
3answers
139 views

Is there a rational surjection $\Bbb N\to\Bbb Q$?

The question is in the title. Is there a one-dimensional rational function $f\in\Bbb R(X)$ which restricts to $\Bbb N\to\Bbb Q$, which is a surjection onto $\Bbb Q$? My guess is no. Expanding the ...
0
votes
3answers
65 views

Find all rational points where $x^2 - y^2 = 1$ (need help simplifying quadratic formula) [duplicate]

The original problem is to find all rational points where $x^2 - y^2 = 1$ I know how to go about the problem, but whenever I get to the point of simplifying my equation, I keep having problems. This ...
0
votes
1answer
36 views

Exercise 3 on page 5 and exercise 7 on page 6 in Koblitz's Introduction to modular forms.

I want to prove $1$ cannot be a congruent number, by using the fact that if it were congruent then the equation $x^4-y^4=u^2$ would have a solution in integers with $u$ being odd. I proved this last ...
2
votes
1answer
63 views

Goldbach Conjecture, what are new research methods after Chen's work?

For Goldbach Conjecture, my understanding is that there are three major methods to attempt it: Schnirelmann density circle method sieve method (Chen used two parameter sieve method to get his ...
3
votes
0answers
40 views

A number $n$ has $12$ divisors and $d_{d_4-1} = (d_1+d_2+d_4)d_8$.

Find a number $n$ which has - $1.$ $12$ divisors $(1 = d_1 < d_2 < \cdots <d_{12}=n )$ and $2.$ $d_{d_4-1}=(d_1+d_2+d_4)d_8$. Note: This is a problem from Russian Mathematical Olympiad ...
0
votes
0answers
20 views

Alternating Series Identity Implications

I am working on a proof for one of my professors and have a vague question about the subject matter. Suppose we have two functions, $f$ and $g$, such that $f: \mathbb N \to \mathbb Q$ and $g: \mathbb ...
0
votes
1answer
107 views

What would the Riemann Hypothesis mean for the Prime Number Theorem?

The Prime Number Theorem states $\pi(n)\sim \dfrac{n}{\ln n}$. Would there be an equally simple expression if Riemann's Hypothesis were proved true? From Chebyshev Function, would $\pi(n)\sim ...
0
votes
0answers
26 views

Find minimum of the sigma

Is there any polynomial algorithm to finding ${x_1,x_2,\dots,x_n}$ for fixed $a_{i,j},p_{i,j},g_{i,j}$ such that minimize $\sum p_{i,j}c_{i,j}$ where : $a_{i,j}+x_i-x_j\equiv c_{i,j} ...
2
votes
1answer
14 views

Decrypting a message using rem()

Hello i have a problem in decrypting a message using this algorithm Beforehand : The sender and receiver agree on a large prime p, which may be made public. (This will be the modulus for all our ...
2
votes
2answers
23 views

Why does this Boolean absorption law work?

It is said that $x \land (x \lor y) = x$ and $x \lor (x \land y) = x$ but I can't see how. When I use distributive law on $x \land (x \lor y)$ I get $(x \land x) \lor (x \land y)$ which is the same ...
2
votes
3answers
92 views

Find a formula for all the points on the hyperbola $x^2 - y^2 = 1$? whose coordinates are rational numbers.

So, I know that we first need to have an initial point. The answers I have say it's $(-1, 0)$ which makes sense because it satisfies the equation. But for example $(1, 0)$ satisfies it too. Why did we ...
0
votes
0answers
46 views

Stirling Approximation: Finding the Error

I was looking at this post Is there a closed-form equation for $n!$? If not, why not?, and I had a question. Is there a way that we can calculate the relative error for the Stirling approximation, ...
4
votes
1answer
60 views

Probability that a number has $m$ indistinct factors

I just discovered Matlab's factor()-function, and I randomly typed in 20081294819, and to my surprise it only had two factors (5099 and 3938281)! I had expected many more factors for such a big number ...
-1
votes
1answer
36 views

How to prove that there is no infinite arithmetic progression of perfect squares

How to prove that there is no infinite arithmetic progression of perfect squares This question from a school Olympiad paper ! How can I prove this directly or using contradiction ? For example : 1 ...
1
vote
0answers
17 views

number formed by inserting odd number of zeros between two ones

we know that $101$ is a prime number. similarly $10001$ is also prime. Can we have a general proof that number with trailing ones and odd number of zeros between them is Prime. That is if ...
1
vote
1answer
21 views

Simultaneously the sum of $2,3,\ldots,k$ distinct fourth powers

Prove that for any positive integer $k\geq 3$ there exists an integer $n$ which is simultaneously a sum of $2, 3, \ldots, k$ distinct fourth powers. I can prove this if we use distinct cubes ...
2
votes
2answers
49 views

Tips for Prime Factorization of a Given Large Interger

This may be a slightly silly question, but are there any tips for prime factorization when slight hints are given? For example, if you were not possesed of pen, paper, or calculator, and somebody ...
0
votes
0answers
29 views

How to prove members of this series differ from an integer by, at most, 1/n?

Consider the series , where a is a positive real number. a, 2a, 3a, .... (n-1)a Prove that there is one member of this series that differs from an integer by at most 1/n. My approach : Draw a ...
0
votes
1answer
49 views

Why solution of $x^2-y^2=702$ is invalid?

If $x$ & $y$ are natural numbers then the no. of ordered pairs $(x, y)$ satisfying $$x^2-y^2=702$$ my try: i factorized $$702=2\times 3^2\times 13$$ so i got $$(x-y)(x+y)=2\times 3^2\times ...
2
votes
3answers
82 views

Why isn't integer factorization in complexity P, when you can factorize n in O(√n) steps?

It is said that integer factorization is an NP problem. Why isn't it P? You can solve it in $O(\sqrt{n})$ time with trial factorization, and since $\sqrt{n} = n^{1/2}$, to me that looks like a number ...
1
vote
1answer
48 views

Infinite sums and Hilbert Schmidt operators

Let $A(H;H)$ be a bounded operator acting from the Hilbert space $H$ to the Hilbert space $H$ such that the eigenvalues of $A$ for a given set of orthonormal eigenvectors $\{e_{i}\}$ in $H$ are given ...
2
votes
3answers
35 views

Modular Arithmetic and Residue Classes

Trying to solve the following: $(2*{4^n})\equiv4\pmod7$ for $n \in \Bbb N$ . Any hints would be appreciated.
0
votes
0answers
43 views

Prime Power Divisibility and Wolstenholme Theorem

In A. Gardiner's paper: Four Problems on Prime Power Divisibility, Amer. Math. Monthly 95(1988),926-931, He said that ``A simple calculation then shows that (for $p\geq5$)'' ...
0
votes
1answer
31 views

Integer Division Solutions

How do you solve this question: For how many integers $x$ is $(x + 49)/(x − 16)$ an integer? Should I set this expression equal to something and then solve? Please explain how I should solve this ...
1
vote
1answer
40 views

$ord_p(x)$ for $\mathbb{Q}$

For a prime $p$ and $x \in \mathbb{Q^{*}}$, define $ord_p(x) = ord_p(n)-ord_p(d)$, where $x = \frac{n}{d}$ with $n, d \in \mathbb{Z}$. (a) Show that $x=\frac{p^ea}{b}$ where $a$ and $b$ are integers ...
1
vote
0answers
42 views

Generate All Triangular Square Numbers Recursively?

We define a triangular number as follows: $$\sum_{n=1}^{n} x_{i}$$ As in $T_3$ = $3+2+1$, or $6$. Generating these triangular numbers is rather simple and done by the equation: $$T_n ={(n^2 + ...
0
votes
1answer
31 views

How to find $n$ if $a^n \equiv r \pmod m$

In particular I'm looking at the problem: \begin{align*} 3^{n_1} &\equiv 1 \pmod 4 \\ 5^{n_2} &\equiv 1 \pmod 4 \\ 7^{n_3} &\equiv 1 \pmod 4 \\ \end{align*} And I want to find $n_1, ...
6
votes
1answer
59 views

Show that for $n$ distinct numbers the following holds

Show that for all $n\in\mathbb{N}$ there exist $a_i\in\mathbb{Z}, i=1,2,\dots,n$ distinct numbers so that: $$\sum_{i=1}^{n}a_i^2=\sum_{i=1}^{n}a_i^3$$ Using normal induction wont bring me anything, ...
1
vote
1answer
38 views

Show that every number $a$ can be shown in the following form: $a=\sum_{i=1}^{k}2^{x_i}\cdot 3^{y_i}$

Show that every integer $a>0$ can be shown in the form: $$a=\sum_{i=1}^{k}2^{x_i}\cdot 3^{y_i}$$ where $0\le x_1< x_2< \dots < x_k$ and $0\le y_k < y_{k-1} < \dots < y_1$ are ...
1
vote
1answer
61 views

Any even is the sume of two primes [duplicate]

How can you prove or disprove that any even number is the sum of two primes?
3
votes
1answer
25 views

Prove that if $x^k \equiv n \pmod {n^2}$ then $n=y^k$ for some $y \in \mathbb{Z}$

I've encountered the following problem: Prove that if $x^k \equiv n \pmod {n^2}$ for some $x\in \mathbb{Z}$, then $n=y^k$ for some $y \in \mathbb{Z}$. I failed to solve it. I tried decomposing $n = ...