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)

6
votes
3answers
498 views

A triangular representation for the divisor summatory function, $D(x)$

Let $d(n)$ represent the divisor function as $d(n)=\displaystyle\sum\limits_{k|n}1$ and the divisor summatory function as $D(x)=\displaystyle\sum\limits_{n \leq x}d(n)$ I found the following ...
2
votes
0answers
21 views

Frobenius automorphism and non-split Cartan subgroup of $\mathrm{GL}_2(\mathbb{F}_p)$

For completeness I give some definitions. Let $p$ a prime number and consider $V$ a 2-dimensional $\mathbb{F}_p$-vector space. Consider $k$ a sub-algebra of $\mathrm{End}(V)$ that is a field of $p^2$ ...
3
votes
2answers
45 views

Indexes of prime Fibonacci numbers

I found this on Mathworld, but I can't seem to find any proof, either on StackExchange, nor any other site: Why do all Fibonacci primes, except for $F_4=3$, have prime indexes (with $F_0=0$)? My ...
6
votes
1answer
66 views

Show that $t^n-1 \mid t^m-1 \Leftrightarrow n\mid m$

I want to prove the following lemma: $t^n-1$ divides $t^m-1$ in $F[t, t^{-1}]$ if and only if $n$ divides $m$ in $\mathbb{Z}$. I have done the following: $\Leftarrow $ : $n\mid m \Rightarrow ...
10
votes
1answer
80 views

Number of polynomial factors of $a^n-b^n$?

This is a number theoretical problem that I discovered myself. Let $f(n)$ be the number of factors of $a^n-b^n$ with integer coefficients when its completely factored. For example: $f(1)=1$, because ...
6
votes
1answer
131 views

$1989|n^{n^{n^{n}}} - n^{n^{n}}$ for integer $n \ge 3$

Before anyone comments, yes this is kind of a duplicate of Prove that $1989|n^{n^{n^{n}}} - n^{n^{n}}$ . The problem that I'm having I don't see the $n=5$ as a counterexample. Also if anyone wants to ...
-1
votes
0answers
36 views

Zero-Sum Partitions of Nonzero Elements of a Ring

In this question, rings are not necessarily finite nor do they need to be unital (i.e., the multiplicative identity may not exist). Although I shall exclusively discuss finite commutative unital ...
4
votes
1answer
124 views

Number theory: $x^y + 1 = y^x$

Today a friend told me the equality: $2^3 + 1 = 3^2$, and I wondered if there exist more solutions to the general problem $$x^y + 1 = y^x$$ where $x$ and $y$ are integers. Some research led me to the ...
50
votes
1answer
2k views

Is this similarity to the Fourier transform of the von Mangoldt function real?

Mathematica knows that the logarithm of $n$ is: $$\log(n) = \lim\limits_{s \rightarrow 1} \zeta(s)\left(1 - \frac{1}{n^{(s - 1)}}\right)$$ The von Mangoldt function should then be: ...
2
votes
1answer
22 views

Fermat primality test and Fermat pseudoprime

What is the difference between Fermat primality test and Fermat pseudoprime?Can anyone explain me how we use them ?
23
votes
2answers
527 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 ...
1
vote
0answers
63 views

Sets with $n$ prime numbers

Let $n>2$ a natural number. We define the following sets: $$S=\{1 \leq a \leq n : (a,n)=1, a^{n-1} \not\equiv 1\pmod n\} \\ T=\{1 \leq b \leq n : (b,n)=1, b^{n-1} \equiv 1 \pmod n\}$$ ...
4
votes
1answer
181 views

Prove that $1989\mid n^{n^{n^{n}}} - n^{n^{n}}$

Having difficulty in proving this: $1989\mid n^{n^{n^{n}}} - n^{n^{n}}$ for all $n \in \Bbb N$. Prime factorization of $1989$ is $3^2 \times 13 \times 17$. Please Help!
3
votes
0answers
69 views

Solutions to $\prod_{i=1}^{k}p_i=\sum_{i=1}^{k}p_i^2$ with $p_i$ distincts primes

Does $\prod_{i=1}^{k}p_i=\sum_{i=1}^{k}p_i^2$ with $p_i$ distincts primes and $k\geq2$ have a solution ? Here is what I already know : There is no solutions if $k\equiv0\bmod2$ or if ...
-1
votes
1answer
20 views

Combining Moebius transformations

Moebius transformation in this case $\frac{az+b}{cz+d}$ for complex $z$. I have several transformations I want to apply to an initial $z$. For example first transform $f(a,b,z) = z + (a + bi) = ...
20
votes
5answers
2k views

Are primes randomly distributed?

There is a famous citation that says "It is evident that the primes are randomly distributed but, unfortunately, we don't know what 'random' means." R. C. Vaughan (February 1990) I have this very ...
0
votes
3answers
27 views

Find the number of seven digit whole numbers in which only 2 and 3 are present as digits if no two 2's are consecutive in any number?

Find the number of seven digit whole numbers in which only $2$ and $3$ are present as digits if no two $2$'s are consecutive in any number? My Approach: We can make numbers and see like: ...
3
votes
0answers
25 views

FRACTRAN for natural numbers

Is there a simple analogue of FRACTRAN that maps a natural number to a natural number, instead of mapping a list of fractions to a natural number? One could use Gödel encoding to translate FRACTRAN ...
0
votes
1answer
28 views

If $500! = 2^m\cdot$N, where N is an odd positive integer, then find $m$

Problem : If $500! = 2^m\cdot$N, where N is an odd positive integer, then find $m$ My approach : Shall we need to expand $500!$ and then find prime factors and see what is the power of 2 in that ...
10
votes
1answer
119 views

why is $\zeta(1+it) \neq 0$ equivalent to the prime number theorem?

Reading through Titchmarh's book on the Riemann Zeta Function, chapter 3 discusses the Prime Number Theorem. One way to prove this result is to check the zeta function has no zeros on the line $z = 1 ...
4
votes
1answer
39 views

Maximal $n$ such the the additive partition with a given product is unique.

Given $n$, there are many tuples with $a + b + c = n,0 < a < b < c$. For large $n$, different tuples may give the same products. E.g. $2+8+9=19=3+4+12,2\times8\times9=144=3\times4\times12$. ...
-4
votes
0answers
35 views

I dont know about cryptography,Help me with cryptography [on hold]

I have just started my cryptography course. But do not have the idea how to start.give me some name of good books. I also want to know the number theory approach on Cryptography. plz help. THANKS
2
votes
1answer
57 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 ...
6
votes
3answers
222 views

Asymptotic density of powers of primes

I'm supposed to compute the asymptotic density of the set \begin{equation} \Pi(x):=\#\{p^k \leq x :p \;prime, k \in \mathbb{N}\} \end{equation} of prime powers less or equal to $x$, that is, compute ...
13
votes
1answer
195 views

Integer solutions to $\prod\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}x_i^2$

Given integers $x_1,\dots,x_n>1$. Let's assume WLOG that ${x_1}\leq\ldots\leq{x_n}$. I want to prove that the only integer solutions to any equation of this type are: $x_{1,2,3 ...
3
votes
1answer
16 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 ...
1
vote
1answer
31 views

Harmonic Identity Evidence

I was recently cleaning up my laptop when I stumbled upon a spreadsheet that I created a while ago at school when I still had an interest in math. Anyway, I remember reaching the following identity ...
4
votes
2answers
108 views

How do we distinguish between characteristic 0 and characteristic p for very large p?

This is a somewhat soft question, apologies if it turns out to be trivial/nonsensical. Background: I was half-asleep one morning, not quite through my first cup of coffee, and thought about the ...
1
vote
0answers
25 views

Is Dirichlets approximation theorem a method for finding a and b or just used to prove stuff?

I am taking an elementary number theory course and there is a problem that asks to find five rational numbers $p/q$ with $|5^{1/3} - p/q|<= 1/q^2$. I made a spreadsheet to solve the problem, but I ...
1
vote
1answer
29 views

A question on arithmetic progressions

Is it true that for every $n \in \mathbb N$ , $\exists N \in \mathbb N$ such that for any subset $A \subseteq \{1,2,...,N\}$ , either $A$ or $\{1,2,..,N\} \setminus A$ contains an arithmetic ...
1
vote
1answer
31 views

Good introductory book for Probabilistic Number Theory

I have a decent high school knowledge of Elementary Number Theory and it is also a subject I love to study. I have a good background in Real Analysis (not Complex Analysis) and Abstract Algbera. I ...
0
votes
0answers
27 views

How can we show the assertion?

Every natural number not of the form $4^n(8m+7)$ where $m$ and $n$ are natural numbers, can be represented as sum of three squares.
-2
votes
1answer
65 views

Other solutions to 1+1 = 2 [on hold]

Under the usual assumptions of maths and the definition of numbers we have 1 + 1 = 2. However if someone is imaginative enough we can find that: 1 + 1 = 1 (Boolean Algebra) 1 + 1 = 10 (Binary ...
1
vote
0answers
27 views

Properties of a Semi-modulo! operation

Let $A$ be an integer with its representation in base $p$ ($p$ may be prime number but not necessarily) described as: $$A=(a_ma_{m-1}\ldots a_1a_0)_{p}$$ We know $A\equiv (a_n\ldots a_1a_0)_{p}\pmod ...
5
votes
2answers
246 views

Inequality involving a product over the primes

Is there someone who is able to prove the following statement? $$\prod_{m=1}^n \dfrac{p_m-1}{p_m} \leq \dfrac{1}{\ln(n)}$$ for all integers $n >1$ where $p_m$ is the $m$-th prime number.
1
vote
0answers
23 views

Calculating $n$-th $q:P(q)=p \in \Bbb P$

Let $P(x)$ denote the number of ways of writing an integer $x$ as a sum of positive integers (where permutation of the array of integers in the sum doesn't count). Ex: $P(1)=1, P(2)=2,P(4)=5$. Let ...
25
votes
3answers
393 views

Can a number be equal to the sum of the squares of its prime divisors?

If $$n=p_1^{a_1}\cdots p_k^{a_k},$$ then define $$f(n):=p_1^2+\cdots+p_k^2$$ So, $f(n)$ is the sum of the squares of the prime divisors of $n$. For which natural numbers $n\ge 2$ do we have ...
2
votes
1answer
50 views

solutions for Diophantine equation for ${k_1} + 2{k_2} + 3{k_3} + … + n{k_n} = n$

Consider the Diophantine equation of the form ${k_1} + 2{k_2} + 3{k_3} + .... + n{k_n} = n$, where ${k_1},{k_2},...{k_n} \in Z^+$ . For a given $n$, how can I obtain the solutions of a given equation? ...
-1
votes
1answer
66 views

What is the inverse function of gcd? [on hold]

Let $a,x,c \in\mathbb{Z}$. If $\gcd(a,x)=c$ where $a, c$ are constants and $x$ is a variable, then what values can $x$ take and how to find those values ?
7
votes
2answers
52 views

$2$-adic sequence converging to $\sqrt{-7}$.

I am trying to construct a sequence in $\mathbb Q_2$ that is formed of rational numbers and converges to $\sqrt{-7}$, to prove that $(\mathbb Q, |\cdot|_2)$ is not complete. My lecturer stated that ...
1
vote
1answer
29 views

Quadratic reciprocity in the case $a=-1$

I am reading the proof the for odd prime $p$, $$ \left ( \frac{-1}{p} \right)_2 = (-1)^{\frac{p-1}{2}} = \begin{cases} 1 \hspace{2mm} \text{for} \hspace{2mm} p \equiv 1 \operatorname{mod} 4 \\ -1 ...
3
votes
1answer
59 views

Find the sum of all primes smaller than a big number

I need to write a program that calculates the sum of all primes smaller than a given number $N$ ($10^{10} \leq N \leq 10^{14} $). Obviously, the program should run in a reasonable time, so $O(N)$ is ...
2
votes
0answers
29 views

Let $f(x)$ be defined over all rationals $x$ in $[0,1]$ and let $F(n) = \sum_{i=1}^n f(\frac in)$

also define $$F^*(n) = \sum_{i=1\,\,(i,n)=1}^n f(\frac in)$$ then prove that $$F^* = \mu * F$$ where $\mu$ is the Möebius function and the $*$ means the Dirichlet convolution. I tried the Bell series ...
0
votes
0answers
37 views

Proofs needed for observations regarding prime-partitionable numbers.

Definition of a prime-partitionable integer taken from W. Holsztynski, R. F. E. Strube, Paths and circuits in finite groups, Discr. Math. 22 (1987) 263-272, doi and apparently the same as in W. T. ...
1
vote
1answer
48 views

Block of integers: Divisibility

Let a < b be natural numbers. Prove that every block of b consecutive natural numbers contains two distinct elements whose product is divisible by ab. (I've proved this) Suppose now a < b < ...
9
votes
2answers
419 views

Prime Numbers and a Two-Player Game

In this question, $\mathbb{N}_0$ is the set of all nonnegative integers. The notation $\mathbb{N}$ is reserved for the set of all positive integers. Alex and Beth are playing the following game. ...
2
votes
3answers
62 views

Diophantine Equation with 3 Variables

Find all solutions to $2x + 3y + 4z = 5$. I know how to do it with two variables, but I'm confused on how to start this with three variables.
1
vote
0answers
34 views

If $p\mid 2^n\pm1$ with $p$ and $n$ relatively prime, then $p$ is a Wieferich prime iff $p^2$ also divides $2^n\pm 1$

The Wolfram Mathworld article on Wieferich primes states: $2^{p-1}-1\equiv 0 \mod p.$ If the first case of Fermat's last theorem is false for exponent $p$, then $p$ must be a Wieferich prime ...
0
votes
1answer
38 views

Chinese Remainder Theorem example

$$x = 4 \bmod 18$$ $$x = 52 \bmod 96$$ $$x = 6 \bmod 20$$ My current algorithm thinks the answer is $x \equiv 1066 \bmod 1440$ but I don't think there should be a solution to this. The algorithm: ...
-6
votes
0answers
50 views

How is named this property of zero parity? [on hold]

How is named then this property of zero parity? Numbers parity Any number, except zero, multiplied twice, is an even number. A pair has two elements. Demonstration: One multiplied ...