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)

-2
votes
1answer
23 views

Any Mersenne prime contains two consecutive 9 digits? [on hold]

The kids with me were each asked to pick a number. It crossed my mind that a smart aleck might answer with a description of some number that we have never actually computed. I remembered that a ...
0
votes
2answers
65 views

Determine all $n$-digit numbers that are divisible by the cyclic permutations of its digits

Given an integer $n \geq 2$, determine all $n$-digit numbers $M_0 = \overline{a_1a_2 \ldots a_n}$ $(a_i \neq 0, i = 1,2,\ldots,n)$ divisible by the numbers $M_1 = \overline{a_2a_3 \ldots a_na_1}$, $...
2
votes
2answers
58 views

Game of replacing number with divisors

In a game , there are N numbers and 2 player(A and B) . ...
1
vote
2answers
59 views

Subset of Coins with maximal value

Let $ n \in \mathbb{N} $ with $ n\ge 3 $ be given. Assume that you have $ k-1 $ coins of value $ 1/k $ for all $ k \in \lbrace 2,\ldots,n \rbrace $. Now you have to choose a subset of these given ...
4
votes
1answer
32 views

Non-negative integer solutions to $4ab-a-b=c^2$

The puzzle is as follows: Problem: Find all non-negative integer solutions to $4ab-a-b=c^2$ My Progress: There is, of course, the trivial solution of $a=b=c=0$, and I suspect there are no more (...
0
votes
0answers
22 views

Application of the theorem about diophantine equations having either infinite or finite solution.

How can i apply the theorem below in an equation like \begin{equation} \label{eq:(4)} 10^{n+3} a - 10^3 a + 999b = (3y)^2. \end{equation} that equation is actually from letting $m = 3$, from the ...
1
vote
2answers
59 views

Generating function for $\sum_{n=0}^{\infty} n^{p} x^n$

I am trying to derive the generating function for $H(x,p) = \sum_{n=0}^{\infty} n^p x^n$ I am trying to solve it with the following logic: (Edited now, trying a new framing) Base case: $$H(x,0) = \...
9
votes
1answer
82 views

A pair of sequences defined by mutual addition/multiplication

Define sequences $\{a_n\},\,\{b_n\}$ by mutual recurrence relations: $$a_0=b_0=1,\quad a_{n+1}=a_n+b_n,\quad b_{n+1}=a_n\cdot b_n.\tag1$$ The sequence $\{a_n\}$ begins: $$1,\,2,\,3,\,5,\,11,\,41,\,371,...
1
vote
2answers
37 views

Dirichlet inverse of $(-1)^n$

I was tinkering around and noticed the Dirichlet inverse of $\,f(n) = (-1)^n$ seems to be $$ f^{-1}(n) = -\mu\!\left(n\,/\,2^{\nu_2(n)}\right)\left\lceil 2^{\nu_2(n)-1} \right\rceil, $$ where $\nu_p(n)...
1
vote
3answers
38 views

The number of $n$-tuples of nonnegative integers $(x_1,\ldots,x_n)$ satisfying the equation $x_1+\cdots+x_n = r$

For given positive integers $r,v,n$ let $S(r,v,n)$ denote the number of $n$-tuples of nonnegative integers $(x_1,\ldots,x_n)$ satisfying the equation $x_1+\cdots+x_n = r$ and such that $x_i \leq v$ ...
6
votes
2answers
62 views

Deriving sum of powers formula using generating functions

Just for fun I wanted to try to derive a formula for the sum of $p$-powers using generating functions, but without using any literature or websites for help. However I do need a small push or hint. ...
5
votes
1answer
46 views

Are the extremas of $h(x)$ global?

It is well known that $li(x)$, the integral logarithm is a very good approximation of $\pi(x)$, the nunmber of primes not exceeding $x$. So, a very good approximation for the probability, that a ...
-2
votes
1answer
120 views

$\sqrt 1+\sqrt 2 +\sqrt 3 +\cdots +\sqrt {2009}$ change a sign to be rational [on hold]

I have this problem: $$\sqrt 1+\sqrt 2 +\sqrt 3 +\cdots +\sqrt {2009}$$ Prove that you need to change ONLY a sign (to convert a $+$ to $-$) of a single square root, for the sum to be rational. EDIT:...
1
vote
2answers
51 views

Find the maximum value that the quantity $2m+7n$ can have

Find the maximum value that the quantity $2m+7n$ can have such that there exist distinct positive integers $x_i$ $(1 \leq i \leq m)$, $y_j$ $(1 \leq j \leq n)$ such that the $x_i$'s are even, the $y_j$...
1
vote
0answers
55 views

Induction Method in a special case of $ n!+1 = m^2 $ (Brocard's Problem)

Context: Brocard's problem is a problem in mathematics that asks to find integer values of $n$ and $m$ for which$$ n!+1 = m^2 \tag{1}$$ Let's define, $$T=\left(\left\lfloor \frac{ (\lfloor\log(n) \...
2
votes
0answers
68 views

A test problem about algebraic integers in complex field

In a recent algebraic test, I meet this problem: Let R be the ring of algebraic integers in C, K is the field of algebraic numbers in C. Let a be an element of K such that the ring R[a] is ...
-1
votes
0answers
30 views

How large number does it take to give a counterexample in number theory? [on hold]

There are many hypotheses in number theory regardless of the truth. I want to know how large number it needs to show a counterexample of certain hypothesis and how large number super-computers can ...
0
votes
2answers
57 views

$(1^n+2^n+3^n+4^n)\mod5$ and using euler totient function to solve this

The problem gives us an integer $n$ which can be extremely large (can exceed any integer type of your programming language) and we need to calculate the value of the given expression . $$(1^n+2^n+3^n+...
4
votes
3answers
109 views

Books for maths olympiad

I want to prepare for the maths olympiad and I was wondering if you can recommend me some books about combinatorics, number theory and geometry at a beginner and intermediate level. I would appreciate ...
2
votes
2answers
41 views

Assuming $a_0 = 0$, $a_1 = 1$, and $ a_{n+2} = 4a_{n+1}+a_{n}$ for $n \geq 0$, prove that $\gcd(a_m,a_{m+1}) = \gcd(a_m,a_{m-1})$

Let $(a_n)_{n \in \mathbb{N}}$ be the sequence of integers defined recursively by $a_0 = 0$, $a_1 = 1$, and $a_{n+2} = 4a_{n+1}+a_{n}$ for $n \geq 0$. Prove that if $\gcd(a_m,a_{m+1}) = d > 1$, ...
3
votes
2answers
67 views

Find the common divisors of $a_{1986}$ and $a_{6891}$

Let $(a_n)_{n \in \mathbb{N}}$ be the sequence of integers defined recursively by $a_0 = 0$, $a_1 = 1, a_{n+2} = 4a_{n+1}+a_{n}$ for $n \geq 0$. Find the common divisors of $a_{1986}$ and $a_{6891}$. ...
1
vote
3answers
32 views

If $p$ and $q$ are odd, prove that there are no integral solutions

Prove that if $p$ and $q$ are odd numbers , then the equation $x^{10} + p x^{​9} + q = 0$ does not have integral solution. Could some hint a simple approach to solve this question. I am not getting ...
4
votes
1answer
97 views

For which values of $n$ the sum $\sum_{k=1}^n k^2$ is a perfect square?

Question. For which values of $n$ the sum $\sum_{k=1}^n k^2$ is a perfect square? Clearly, $n=24$ is one such value, and I was wondering whether this is the only value for which the above holds. The ...
1
vote
1answer
55 views

Strange results in mersenne.org database

I am interested in GIMPS project. I was browsing through known Mersenne prime numbers when I discovered strange records in their database. For example, M6972593 is the 38th Mersenne prime. However, ...
0
votes
1answer
47 views

Prove that $\text{ord}_{2^n}(x) = 2^k$

Let $p$ be a prime. Define $v_p(x)$ such that if $v_p(x) = n$, then $p^n \mid x$ but $p^{n+1} \nmid x$. Prove that if $v_2(x^{2^k}-1) = n$ where $\gcd(x,2^n) = 1$, then $\text{ord}_{2^n}(x) = 2^k$. ...
0
votes
0answers
12 views

Distribution of numbers of the form $p^{q-1}$, p and q prime

Prime numbers are exactly the integers having 2 divisors and of course, 2 is itself prime. If one considers the set of positive integers with a prime number of divisors, one can easily figure out that ...
0
votes
1answer
29 views

Mapping finite discrete numbers to the infinite set

This is an extension of my earlier question: Mapping discrete numbers Given that we can "map" $\mathbb{N}$ to $\mathbb{Z}$ via a bijection, I then wondered if it is possible to map a small subset of $\...
1
vote
1answer
43 views

Prove that the Area of triangle whose vertices are $(0,0)$, $(b,a)$ and $(x,y)$ is $|by-ax|/2$

Prove that the Are of triangle whose vertices are $(0,0)$, $(b,a)$ and $(x,y)$ is $\displaystyle \frac{|by-ax|}{2}$. I found this problem in Number theory by George Andrews, but I wonder how it ...
1
vote
0answers
36 views

Factors vs distinct factors

I have a doubt in questions where we are asked to find the number of distinct factors of a number. Do we have to consider the total number of factors which are positive factors + negative factors ...
0
votes
2answers
19 views

Mapping discrete numbers

I would like to find a way to map the natural numbers, $\mathbb{N}$, to integers, $\mathbb{Z}$, and vice-versa. An analogous solution for continuous numbers would be using the $\log()$ and $\exp()$ ...
0
votes
0answers
58 views

A conjecture relating to Goldbach

I have a conjecture related to the strong Goldbach conjecture and the Goldbach function. It is that: for any $g(E)$, there are a finite number of even numbers which can be expressed as a sum of two ...
6
votes
1answer
196 views

$m^2+2017=n^3$ has no solutions

Show that $m^2+2017=n^3$ has no solutions for positive integers $m,n$. I'm having trouble tackling this one, especially since $\mathbb{Z}[\sqrt{-2017}]$ isn't a UFD. We can write the equation as $m^...
2
votes
2answers
32 views

Why is the number of common divisors of two numbers equal to the number of divisors of their GCD?

I've searched a lot but I am not able to find a simple explanation. If you can, please explain it in an intuitive manner. Thanks
11
votes
3answers
179 views

Decompose $5^{1985}-1$ into factors

Decompose the number $5^{1985}-1$ into a product of three integers, each of which is larger than $5^{100}$. We first notice the factorization $x^5-1 = (x-1)(x^4+x^3+x^2+x+1)$. Now to factorize $x^4+...
1
vote
2answers
27 views

Consecutive integers in $S_n:=\{\sum_{i=1}^{n}x_i^n\ \mid\ \left(x_1,…,x_n\right)\in\mathbb{N}^n\}$

Define for $n≥2$ the set $S_n$ to be $S_n:=\{\sum_{i=1}^{n}x_i^n\ \mid\ \left(x_1,...,x_n\right)\in\mathbb{N}^n\}$ where $\mathbb{N}=\{1,2,3,...\}$. What is the longest sequence of consecutive ...
4
votes
1answer
63 views

What is the computational complexity of calculating $\pi(x)$ exactly?

The prime counting function $\pi(x)$ has been determined for $x=10^{26}$. The list of the $10^n$-th primes , however , ends at $n=18$. The $10^{18}$-th prime has $20$ digits. Apparantly, the ...
1
vote
5answers
91 views

Integer solutions to $5m^2-6mn+7n^2 = 1985$

Are there integers $m$ and $n$ such that $$5m^2-6mn+7n^2 = 1985?$$ Taking the equation modulo $3$ gives $n^2-m^2 \equiv 2 \pmod{3}$. Thus, $3 \mid n$ but $3 \nmid m$. How can I use this to find a ...
1
vote
1answer
39 views

Adding the reverse of digits

You start with an integer $n$. Repeat the following process $i$ times: $n=$ $n+\text{the reverse of n} $ By 'reverse' I mean the digits of the number are flipped, ie $123 \rightarrow 321$. Is there ...
1
vote
2answers
33 views

How to compute variance of a conditional expectation and vice versa

I am trying to use the law of total variance which is $$\operatorname{Var}(X) = \text{Var}(E(X\mid Y)) + E(\operatorname{Var}(X\mid Y))$$ But I honestly have no idea how to compute either one of ...
1
vote
1answer
69 views

Parity of $\sum_{i=1}^{n}\lfloor \log_2(i) \rfloor$

Let, $L=\sum_{i=1}^{n}\lfloor \log_2(i) \rfloor $. Problem: Find $n$ for which $L$ is odd. In other words, find a closed form expression (function) $f(n)$of variable $n$ such that $L$ is odd/even if ...
3
votes
2answers
33 views

Determining whether an element belongs to ring of integers

Consider a number field $K=\mathbb{Q}[\alpha]$ and we wish to show that some other element $\beta \in K$ belongs to the ring of integers $\mathcal{O}_K$. Is it enough to show that the norm and trace ...
0
votes
1answer
20 views

Help with Linear Congruence Problem

I'm solving a larger (programming) problem in which I'm trying to work on my own solution which involves involves a smaller number theory problem and would like some help on the smaller problem by ...
-1
votes
0answers
33 views

Multiplicative implication of Goldbach's conjecture?

I've recently been thinking what would goldbach's conjecture imply in multiplicative expression: We start by stating Goldbach's conjecture in terms of the powers of a polynomial: $$ f(x)^2 = (\sum_{...
7
votes
0answers
113 views

Can $\sqrt[n]{\sqrt{a}+\sqrt{b}}+\sqrt[n]{\sqrt{a}-\sqrt{b}}$ be an integer?

The number $\sqrt{a}+\sqrt{b}$ cannot be an integer if $a,b$ are integers such that $\sqrt{b}$ is not an integer. (In fact, this is true for any number of square roots, and I believe even for cube ...
0
votes
0answers
33 views

For prime >2, is there always a power of a prime which is a primitive root? [closed]

As the title, I'm trying to find the answer about this question. However, I can't google anything :( Thanks! EDIT: this primitive root must less than the prime
1
vote
1answer
29 views

Find the gcd of the following Gaussian integers

$\gcd(5 + 8i, 3 + 2i)$ in $Z[i]$. I found it and I got 1 then I look at the manual solution and it turns out it can be i or -i or -1 or 1. why?
0
votes
1answer
38 views

Proof about Gaussian integers

Show that if $\lambda \in Z[i]$ and $Norm(\lambda)=p$ where p is a prime number then $\lambda$ is prime in $Z[i]$ Approach: not so much to say $\lambda=a+bi$ where a and b are integers, so $N\lambda=...
10
votes
3answers
92 views

Show that $a_n = [n \sqrt{2}]$ contains an infinite number of integer powers of $2$

Show that the sequence $\{a_n\}_{n \geq 1}$ defined by $a_n = [n \sqrt{2}]$ contains an infinite number of integer powers of $2$. ($[x]$ is the integer part of $x$.) I tried listing out the first ...
3
votes
0answers
49 views

little Fermat theorem generalization proof without Burnside's lemma

Burnside's Lemma Deduce That: $$\sum_{i=1}^n a^{gcd(i,n)} $$ is divisible by $n$ it's a beautiful result. but i want to prove it without any abstract algebraic tools such as Burnside's Lemma... is ...
8
votes
0answers
95 views

How many ways can I arrange the numbers $1$ to $N$ with this divisibility condition?

For the numbers $1, \ldots, N$, how many ways can I arrange them such that either: The number at $i$ is evenly divisible by $i$, or $i$ is evenly divisible by the number at $i$. Example: for N = 2$...