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
11 views

Arithmetic function corresponding to a specific Dirichlet convolution

Does the function $f := \mu \ast (\tau \cdot \text{id}) = \mu \ast \text{id} \ast \text{id} = \phi \ast \text{id}$ equal (or can be written in terms of) any of the common arithmetic functions? Here ...
0
votes
0answers
6 views

$S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$, $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ iwth composite and prime numbers

I have two sets with $n>2$ natural number: $S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$ $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ Can anyone explain me if there are prime ...
3
votes
1answer
59 views

The existential theory is undecidable

Lemma 1. For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and ...
1
vote
0answers
39 views

Are logarithms of prime numbers algebraically independent?

From Baker's theorem it follows that a linear combination of natural logarithms of prime numbers with non-zero algebraic coefficients can never be zero. Has it been proved that the set of all natural ...
-3
votes
2answers
48 views

All natural numbers $m, n$ such that $m = \sqrt{\frac{1}3A^2 - 3n^2}$ [on hold]

I have $m = \sqrt{\frac{1}3A^2 - 3n^2}$. A is a known integer. How do I find all solutions for what m and n are if both m and n are naturals (round positive numbers)
18
votes
1answer
213 views

Is $1992! - 1$ prime?

Consider the factorials, defined inductively by $1! = 0! = 1$ and $n! = n\cdot(n-1)!$ for $n \geq 2$. Question: Is $1992!-1$ a prime number? The question is from a book, maybe is contest math ...
2
votes
1answer
38 views

Proof of Cohn's Irreducibility Criterion

I was looking for an elementary (or involving introductory level abstract algebra/analysis) proof of Cohn's Irreduciblity Criterion: If $$ a_0, a_1, \dots, a_n \in \Bbb{Z} $$ and $$ 0 \le ...
0
votes
3answers
29 views

Finding the largest square divisor of a number

My calculator has the option of representing square roots in the form of $a\sqrt b$, when $a$ is maximal. It works for very large inputs within seconds, and I wonder how it's being done.
0
votes
1answer
35 views

NumberTheory: Proof or disproof the following. Dividing and adding

Proof or disproof the following. Let $N \in \mathbb{N}$ be a natural number. If we divide the digits of $N$ with preserving the order and adding them together we will get a digit ( a number less ...
3
votes
1answer
68 views

Are the real number $\sqrt{6}$ in $\mathbb{R}$ equal to the 5-adic number $\sqrt{6}$ in $\mathbb{Q}_5$?

My question is as in the title. That is, consider solving the equation $x^2-6=0$ in $\mathbb{R}$ and in the 5-adic field $\mathbb{Q}_5$ respectively. We obtain one $\sqrt{6}\in\mathbb{R}$ and one ...
1
vote
1answer
26 views

Asymptotic probability that two integers are coprime

I'm having difficulty with a number-theory-type exercise. Could you provide assistance with computing the asymptotic probabilities that two integers are coprime (both integers tending to $\infty$), ...
1
vote
0answers
36 views

Is the Green-Tao theorem valid for arithmetic progressions of numbers whose Möbius value $\mu(n)=-1$?

I am reading the basic concepts of the Green-Tao theorem (and also reading the previous questions at MSE about the corollaries of the theorem). According to the Wikipedia, the theorem can be stated ...
3
votes
2answers
30 views

Congruence rules when solving equation

I am trying to solve the following congruence problem. 980x ≡ 1500 mod 1600 The steps I came up with were as follows: 980x ≡ 1500 mod 1600 49x ≡ 75 mod 80 (Divide by 20, gcd(20, 1600) = 20 so 80 = ...
0
votes
0answers
43 views

Prove that $n \in \mathbb{Z}^\star \Leftrightarrow n \mid 1$ and $n-1 \mid 1$ or $n+1 \mid 1$, and $(x-1)/(t-1) \equiv n \pmod {t-1}$

I want to prove the following lemma: Let $F[t,t^{-1}]$ be the ring of the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$ and assume that the characteristic of $F$ is zero. ...
0
votes
0answers
20 views

On Period of Linear Recurring Sequences modulo $P^e$

If a sequence $ X_0,X_1,X_2,\ldots$ is defined in terms of an initial set $ X_0,X_1,X_2,\ldots ,X_{k-1} $ by the recurrence relation $$ X_{n+k}= ...
1
vote
1answer
13 views

Comparison of arbitary conway chains (in particular a chain with $m$ $m's$) to $f_{\omega^2}(n)$

Wikipedia describes the Conway chained arrow notation and the fast growing hierarchy. I learnt that the function $f(n):=\large f_{\omega^2}(n)$ has the same growth rate as the function ...
0
votes
1answer
33 views

sum of the series of certain form close to Fermat's numbers

My question is: What is the sum of reciprocals of the numbers $2^{2^n}$. If we achieve this we will be able to give a good bound for the sum of reciprocals of Fermat's numbers i.e. $(2^{2^n})$+1.
1
vote
1answer
17 views

Why the action of $\mathrm{Gal}(\overline{\mathbb Q}_p/\mathbb Q_p)$ on $\overline{\mathbb Q}_p$ restricts to $\overline{\mathbb Q}$?

Let $\overline{\mathbb Q}$ be the algebraic closure of $\mathbb Q$ in $\mathbb C$ and chose an algebraic closure $\overline{\mathbb Q}_p$ for $\mathbb Q_p$. The embedding $\mathbb Q \hookrightarrow ...
4
votes
0answers
32 views

Motivation behind the Archimedean norm on number fields .

It is easy to justify the use of non-archimedean norms on number fields from an "inside view" as arising from the prime ideals and are therefore clearly useful a priori. However, it seems to me that ...
1
vote
0answers
6 views

Does $F\otimes G\in\mathcal{M}$?

Let $\mathcal{M}$ be the class of automorphic L-functions which belong to the Selberg class. Let $F$ and $G$ be elements of this class, and define $F\otimes G$ by $a_{p}(F\otimes G)=a_{p}(F).a_{p}(G)$ ...
0
votes
2answers
15 views

Does changing the value of x change the number of solutions?

So I have the equation: $$-C<2n+x<C$$ Where $$n ∈ Z$$ $$C ∈ R$$ $$-1<x<1$$ My question is, for a given value of C, do the same number of values for n always exist, regardless of the ...
3
votes
0answers
42 views

Which permutations of $\mathbb{C}$ commute with the Riemann zeta function?

I'm trying to figure out whether the permutations of $\mathbb{C}$ which commute with the Riemann $\zeta$ function are necessarily continuous or not. Obviously both the identity and the complex ...
2
votes
1answer
33 views

Generalization of Erdos-Selfridge

Consider the equation $P(x)=y^d$ where $d \geq 2$ is an integer and $P$ can be written $P(x)=c(x-r_1)(x-r_2)\ldots (x-r_t)$ where $c$ and all the $r_i$ are integers not all equal (some of them can be ...
4
votes
0answers
61 views

On a unique(?) binomial property of $3003$

Given the triangular number, $$T_k = \frac{k(k+1)}{2}$$ and remembering that, $$\binom{n}{m}=\binom{n}{n-m}$$ Excluding $a_0=1$, we then have the six-fold (at least) equalities, $$\begin{aligned} ...
2
votes
0answers
21 views

$x-y^4= LCM(x, y)$ [duplicate]

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with the least common multiple, but other than that, the textbook gave no hints ...
0
votes
1answer
53 views

Pairs of integers with gcd equal to a given number

Given integers $N$ and $D$, find how many pairs of integers $(i, j)$ such that $1 \le i \le j \le N$ have the greatest common divisor exactly $D$. I know it involves Mobius inversion somehow, but I ...
-2
votes
1answer
45 views

Describe a fast (polynomial time)algorithm who takes as input the elements $g^a,g^b$ and gives as output the element $g^{a \cdot b}$

Let $q$ prime number, $G$ a cyclic group with order $q$ and $g \in G$. Suppose that you have an algorithm $A$ who takes input the element $g^a$ of $G$ and gives as output the element $g^{a^2}$. ...
2
votes
0answers
56 views

A lower bound for an arithmetic function

Let $N \in \mathbb{N}$ such that $\phi(N) \sim N$, where $\phi$ is the Euler's totient function. Let $A \subset [N] := \{1, 2, \ldots, N\}$. For $n \in \mathbb{N}$ define the function $$ C_A(n) = \#\{ ...
0
votes
0answers
53 views

System of equations to solve this nested radical.

The nested radical $$1.75793\approx\sqrt{1+\sqrt{2+\sqrt{3+\cdots}}}$$ has yet to be given a closed form. However, nested radicals of the form, $$\sqrt{A+B\sqrt{A+B\sqrt{A+\cdots}}}$$ have the ...
3
votes
2answers
57 views

The algebraic closure of $\mathbb{Q}_p$

I am trying to explain why $\mathbb{Q}_p^{\text{alg cl}}$ is an infinite field extension of $\mathbb{Q}_p$ (unlike $\mathbb{C}/\mathbb{R}$ which has deg 2). Does the following argument work out... ...
-1
votes
2answers
41 views

problem of number theory N. Sato [on hold]

Can someone help me solve this problem? Sato, 4.2. For an odd positive integer $n>1$, let $S$ be the set of integers $x$ such that $1 \leq x \leq n$, such that both $x$ and $x+1$ are ...
1
vote
3answers
56 views

Upper bound for prime-counting function: $ \pi(n)\le\frac{n}{3}+2 $

$ \pi(n)\le\frac{n}{3}+2 $... Could someone explain me, how to prove it? I'm completely stuck, as informations I found on Wikipedia aren't very clear to me. (I was able to prove that for sufficiently ...
1
vote
0answers
37 views

How many composite pairs $(6n-1, 6n+1)$ in the range $[5, 6(1+35t)+1]$ for large $t$

I would like to find out that how many composite pairs $(6n-1,\, 6n+1)$ are their in the range $[5, 6(1+35t)+1]$ for large $t$. Total composite pairs should be a function of t. For example, ...
0
votes
3answers
42 views

proof for divisibility

Prove without the use of congruences that $341$ divides $2^{340} - 1$. This was a question I found in a book right after which Fermat's little theorem is discussed. I tried using it for the proof but ...
0
votes
1answer
29 views

What does the symbol $N(\mathfrak{p}_{i})=P^{k_i}$ mean in theorem of Dedekind?

When I was reading an article about linear recurrence relations, I saw this notation: $$P=\mathfrak{p}_1^{e_1}\mathfrak{p}_2^{e_2}...\mathfrak{p}_r^{e_r}$$ $$ N(\mathfrak{p}_{i})=P^{k_i}$$ What is ...
5
votes
1answer
93 views

Maybe hard than IMO 2015 problem 2

Find all postive integers $(a,b,c)$ , such that$a^2b-c,b^2c-a,c^2a-b$ are all powers of 2 someone can take a example such this condition
0
votes
0answers
22 views

With a sequence $\{B_n\}$ and a function defined on all of its elements, what are the spaces between the outputs of the function?

I have a sequence $\{B_n\}$ and a function defined for every member of that sequence: $f(B_i,C_j)=a_j^i$ (Where the spaces between any two adjacent $C$'s is always constant). Such that the following ...
0
votes
2answers
48 views

A tricky diophantine equation with factorials

I am being unable to solve this diophantine equation. Does anyone have any suggestions. Let $n$ and $m$ both be non-negative integers. Find all solutions to $$n(nm - 2)! = (n!)^m$$ How would one ...
0
votes
0answers
3 views

Successive divisibility of a sequence? Progressive divisibility? terminology or reference

Perhaps I say that an (infinite) sequence $(r_n)$ of positive integers is progressively divisible iff $r_n \mid r_{n+1}$ for all $n$. Is there some other terminology that is in use for this? I am ...
0
votes
2answers
56 views

How to check this number $\sqrt{47}$ is irrational [duplicate]

Prove that $\sqrt{47}$ is irrational number. I know that a rational number is written as $\frac{p}{q}$ where $p$ & $q$ are co-prime numbers. But I do not have any idea to prove it irrational ...
1
vote
0answers
16 views

Number of solutions to quadratic congruence

For every positive integer $b$, show that there exists a positive integer $n$ such that the polynomial ${x^2} - 1 \in (\mathbb{Z}/n\mathbb{Z})[x]$ has at least $b$ roots. My efforts Let $n = ...
3
votes
0answers
29 views

Fractional Part Inequality

How can I show that the following inequality holds when $x$ and $y$ are coprime positive integers greater than 2, and $r$ is an arbitrary rational number greater than or equal to $2$? ...
-1
votes
0answers
57 views

Has there been further attempts to abstract prime numbers?

Ulam's Spiral is a wonderful discovery. Obviously it shows a blurry visual order, or pattern to prime numbers. Why has there been no further developments in refining this underlying pattern? If the ...
2
votes
2answers
51 views

If $n$ is a perfect square number then $\sigma(n)$ is odd number.

How to prove that if $n$ is a perfect square number then $\sigma(n)$ is odd number. This $\sigma(n)$ is the sum of all divisors of $n$.
2
votes
1answer
31 views

$\frac{\sigma(n)}{n}=\frac{5}{3}\,\,\,\Rightarrow\,\,\,\,$ $\sigma(5n)=10n$

Let $n$ a positive integer so that $$\frac{\sigma(n)}{n}=\frac{5}{3}$$ Show that $5n$ is a perfect number i.e $\sigma(5n)=10n$. Note: $\sigma(n)$ is the sum of all positive divisors of $n$.
1
vote
0answers
42 views

On the size of rational numbers and Irrational numbers. [duplicate]

Being a high school student, It's obvious to me that there are both an infinite number of rational and irrational numbers. However I don't really see if there is more rational than irrational, ...
0
votes
1answer
29 views

If $p$ is a prime number and $p\equiv 1(mod 4)$, (show that) there exist integers $a$ and $b$ such that $a^{2}+b^{2}=p$.

I'm reading a book on number theory (Theory of Numbers, Niven), and yesterday I've stumbled upon a proof of the above lemma (Lemma 2.13; page 54-55). I've managed to wrap my mind around the proof from ...
3
votes
1answer
49 views

Positive Integers Equation

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with the least common multiple, but other than that, the textbook gave no hints ...
0
votes
1answer
46 views

What is the relative density of the abundant numbers in the positive integers?

The Art and Craft of Problem Solving by Paul Zeitz has the following problem. Now, I have been able to solve parts (a) and (b), part (a) by showing that it can get arbitrarily large, and part (b) by ...
2
votes
1answer
27 views

How find all finite sets $ M$ such that $ |M|\ge 2$ and $ \frac {2a}{3} - b^2\in M$ for all $ a,b\in M$

How find all finite sets of real numbers $ M$ such that $ |M|\ge 2$ and $ \frac {2a}{3} - b^2\in M$ for all $ a,b\in M$?