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)

4
votes
3answers
49 views

Not understanding the wrong logic in this proof

The problem is : Suppose $a,b \in Z$. If $a^2 + b^2 $ is a perfect square, then $a$ and $b$ are not both odd. My question is why can't I answer like so: Proof by Contradiction -- Suppose $a^2 + b^2 ...
2
votes
0answers
52 views

conjectured arithmetic properties of some continued fraction

Given the continued fraction $$G(q)=\cfrac{1}{1-q+\cfrac{q(1-q)^2}{1-q^3+\cfrac{q(1-q^2)^2}{1-q^5+\cfrac{q(1-q^3)^2}{1-q^7+\ddots}}}}$$ Where $q\lt1$,it is conjectured that the following properties ...
3
votes
1answer
12 views

Maximum length of a string that has no substring divisible by a prime number $p$ is $p-1$?

What is the maximum length of a string of nonzero digits that has no substring that is divisible by a given prime number? I want to find a string of length n which has no substring divisible by the ...
4
votes
2answers
37 views

Which primes $p$ divide $q^q-1$ for a prime divisor $q$ of $p-1$

I am looking for (a formula) for all the primes $p$ less than or equal to $X$ with the following criteria: There is at least one prime $q$ dividing $p-1$ such that $p$ divides $q^q-1$. $7$, for ...
0
votes
2answers
36 views

Getting characteristic polynomial from a small matrix

Sorry I don't know how to format matrices, but if I have this matrix $\pmatrix{1& 1& 0\\ 0& 0& 1\\ 1 &0& 1\\}$ How is the characteristic polynomial $λ^3 − 2λ^2 + λ − ...
0
votes
1answer
10 views

Matrix for a recurrence

The matrix for a recurrence of the form $a_{k+2} = ka_{k+1}+a_{k}$ where $a_0 = 0$ and $a_1 = 1$ is given by $$\begin{bmatrix}k & 1\\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} a_{k+1} & a_k \...
-2
votes
1answer
18 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
58 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}$, $...
1
vote
2answers
42 views

Game of replacing number with divisors

In a game , there are N numbers and 2 player(A and B) . ...
0
votes
1answer
23 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
29 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
17 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
54 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) = \...
8
votes
1answer
54 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
36 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
37 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$ ...
5
votes
1answer
56 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
40 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
119 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
53 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) \...
1
vote
0answers
58 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
29 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
52 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
106 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
38 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
94 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 ...
0
votes
1answer
52 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
35 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
56 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
183 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
169 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
57 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
89 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
38 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
68 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 ...
2
votes
2answers
29 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 ...
0
votes
0answers
32 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
112 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 ...