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
1answer
390 views

How to determine the key-matrix of a Hill cipher where the encrypted-message-matrix is not invertible?

I am new to this subject and I have a homework problem based on Hill cipher, where encryption is done on di-graphs (a pair of alphabets and not on individuals). The alphabet domain is $\{A\dots ...
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$), ...
2
votes
1answer
36 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 ...
36
votes
3answers
620 views
+200

Prove that there exist infinitely many integers $(n^{2015}+1)\mid n!$

I conjecture that there exist infinitely many integers $n$ such that $$(n^{2015}+1)\mid n!.$$ I have seen a simpler problem that there exist infinitely many integers $n$ such that $(n^2+1)\mid ...
3
votes
2answers
37 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 = ...
1
vote
0answers
46 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
55 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 ...
14
votes
0answers
352 views

Which harmonic numbers have prime numerators?

Let $$1+\frac12+\frac13+\cdots+\frac1n=\frac{q}{p}$$ with $(p,q)=1$ and $q$ is a prime number. (I) Prove or disprove that the quantity of $n$ is limited (II) Find all of the $n$ I use the matlab ...
1
vote
1answer
15 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 ...
-3
votes
1answer
47 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}$. ...
0
votes
1answer
34 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.
8
votes
1answer
987 views

Relationship between Primes and Fibonacci Sequence

I recently stumbled across an unexpected relationship between the prime numbers and the Fibonacci sequence. We know a lot about Fibonacci numbers but relatively little about primes, so this connection ...
1
vote
1answer
21 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
37 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 ...
0
votes
2answers
16 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 ...
9
votes
1answer
122 views
+150

Every non-increasing sequence of polynomial towers stabilizes — Finitary proof

In this question we are concerned only with positive integers $\mathbb N$ and other finitary objects that can be encoded using integers. A term function means a total computable function $\mathbb ...
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)$ ...
3
votes
0answers
44 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 ...
9
votes
0answers
165 views

Maximum integer not in $\{ ax+by : \gcd(a,b) = 1 \land a,b \ge 0 \}$

Ryan asked about a variation of the coin problem, which was whether for any coprime natural numbers $x,y$ every sufficiently large natural number is $ax+by$ for some coprime natural numbers $a,b$. ...
4
votes
0answers
71 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} ...
1
vote
0answers
39 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
1answer
58 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
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 ...
8
votes
3answers
249 views

Show that $\pi =4-\sum_{n=1}^{\infty }\frac{(n)!(n-1)!}{(2n+1)!}2^{n+1}$

Show that $$\pi =4-\sum_{n=1}^{\infty }\frac{(n)!(n-1)!}{(2n+1)!}2^{n+1}$$ I found the formula of $\pi$ by using the numerical calculation but I dont have the proving. Any help would be appreciated.
-1
votes
2answers
42 views

problem of number theory N. Sato [closed]

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
62 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 ...
0
votes
1answer
32 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 ...
4
votes
4answers
147 views

Semiprime numbers which, along with their prime factors, generate many semiprimes by concatenation

There's something quite interesting about the number $1191$: this number is a semiprime ($1191= 3 \cdot 397$), the concatenation of its prime factors in any order are semiprimes ($3397$ and $3973$ ...
1
vote
1answer
57 views

Proof of direct sum of ideal class group of Neukirch book

In books Neukirch, Algebraic Number Theory. I don't understand. 1) Why there exists $a$ such that $a\equiv c \ \mod \mathfrak p $ and $a\in ca_{\mathfrak p}^{-1}a_{\mathfrak q}$ for $\mathfrak ...
6
votes
2answers
311 views

Smallest Positive Integer Not Coprime to a Collection of Consecutive Integers

Let $n\in\mathbb{N}$. Define $f(n)$ to be the smallest positive integer $m$ such that there exists a positive integer $k$ for which $k+i$ is not relatively prime to $m$ for every ...
0
votes
3answers
45 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 ...
5
votes
3answers
119 views

Generalize multiples of $999…9$ using digits $(0,1,2)$

The smallest $n$ such that $9n$ uses only the three digits $(0,1,2)$ is $1358$, giving a product $12222$. For $99n$ this is $11335578$, giving $1122222222$. Similarly, ...
5
votes
1answer
57 views

Estimate of an exponential sum involving the Von Mangoldt function

Let $f(x)$ be a polynomial in $\mathbb{Z}[x]$. Define $$ S(\alpha) = \sum_{1 \leq n \leq N} \Lambda(n) e^{2 \pi i f(n) \alpha}. $$ I was wondering how does one obtain that $$ \left( \int_0^1 S(\alpha) ...
5
votes
1answer
96 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 ...
53
votes
2answers
1k views

Can $\sqrt{p}^{\sqrt{p}^{\sqrt{p}}}$ be an integer, if $p$ is a non-square positive integer?

Can $\sqrt{p}^{\sqrt{p}^{\sqrt{p}}}$ be an integer, when $p$ is a non-square positive integer? Of course, it seems it would never but is there a proof of the fact, or maybe we have some spooky $p$ ...
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 ...
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
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 = ...
0
votes
0answers
4 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 ...
1
vote
2answers
59 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 ...
5
votes
4answers
270 views

Check whether $\sum\limits_{n=1}^{\infty}\frac{z^n}{(1-z^n)^k}=\sum\limits_{n=1}^{\infty}\sigma_{k-1}(n)z^n$

Is it true that $$\sum_{n=1}^{\infty}\frac{z^n}{(1-z^n)^k}=\sum_{n=1}^{\infty}\sigma_{k-1}(n)z^n$$ If yes, how can I prove it?
2
votes
2answers
52 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$.
0
votes
0answers
28 views

A better lower bound for $\prod_{i=1}^{k} p_i^2\over \sum_{i=1}^k p_i^2$

I search a better lower bound for $\prod_{i=1}^{k} p_i^2\over \sum_{i=1}^k p_i^2$ with $k>1$ and $p_i$ distinct sorted primes ($p_1<p_2<...<p_k$). By now my lower bound is : ...
0
votes
1answer
33 views

Wieferich prime-Lang-Trotter conjecture connection?

Crandall-Dilcher-Pomerance prediction states that the number of Wieferich primes $<x$ is $log\ logx $ N.Katz in "WIEFERICH PAST AND FUTURE" states; The Crandall-Dilcher-Pomerance prediction is ...
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
47 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
32 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$.
0
votes
0answers
19 views

ElGamal signature for finding the private key

Alice uses an ElGamal signature with base the group $Z^*_{107}$ and parameter $g=3$ of order $q=53$.The private key of Alice is some $x \in \{0,1,.....,52\}$ and the public key of her is $y=10$.To ...
3
votes
1answer
55 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 ...