Questions on more advanced topics of number theory. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.

learn more… | top users | synonyms (1)

3
votes
0answers
75 views

Is it true that for infinitely many values of $n$, the sum of digits of $2^n$ is greater than for $2^{n+1}$?

Let $S(n)$ denote the digit sum of the integer $n$, using base $10$. How to prove that there exist infinitely natural numbers such that $S(2^n)>S(2^{n+1})$? Remarks (by Deven Ware): This is ...
0
votes
2answers
34 views

Proving that any common multiplication of two numbers is a multiplication of their least common multiplication

Im trying to prove that if there are to numbers $n,m$ (natural numbers), and their smallest common multipe is $k$, so that $k = n·i$ and $k = m·j$ for some $i,j$ natural numbers, any common multiple ...
1
vote
1answer
30 views

Sums involving square of Moebius function

I try to estimate the following sum: $$ \sum_{n \leq x}\mu(n)^2 f(n) $$ where $\mu(n)$ is a Moebius function and $f(n)$ is some multiplicative arithmetic function. If I understand it correctly it is ...
0
votes
0answers
29 views

Iterative function eventually reaching identity

For integers $a,b$ we define $f((a,b))=(2a,b-a)$ if $a<b$ and $f((a,b))=(a-b,2b)$ if $a\geq b$. Given a natural number $n>1$ show that there exist natural numbers $m,k$ with $m<n$ such that ...
4
votes
2answers
78 views
+50

Difficult generating function

Define a beautiful number to be an integer of the form $a^n$, where $a\in\{3,4,5,6\}$ and $n$ is a positive integer. Prove that each integer greater than $2$ can be expressed as the sum of pairwise ...
1
vote
1answer
47 views

How to have this equation $s^2-2(p+q+r+2pqr)s+(p^2+q^2+r^2-2(pq+qr+rp)-4)=0$?

Old Question: For $x,y,z\in N^{+}$, if such $(xy+1)(yz+1)(zx+1)$ is a perfect square ,show that $$(xy+1),(yz+1),(xz+1)$$ are all perfect square . and I konw this PDF have solution, ...
7
votes
3answers
269 views

Finding the all integer solutions

How to Find the all integer solutions for: $$x+y+z=3$$ $$x^3+y^3+z^3=3$$
14
votes
4answers
239 views
+500

An inequality on sequences with each term dividing sum of two neighbouring terms

Positive integers $x_1, x_2, \dots, x_n$ ($n \ge 4$) are arranged in a circle such that each $x_i$ divides the sum of the neighbors; that is $$\frac{x_{i-1}+x_{i+1}}{x_i} = k_i $$ is an integer for ...
2
votes
2answers
87 views
+100

Fibonacci number ending with given sequence of digits

Related to this question: For any given sequence of digits, does a Fibonacci number exist ending with such sequence? If not, it would be nice to find the smallest counterexample. (in other ...
0
votes
0answers
54 views
+50

How prove this $3^{\frac{5^{2^n}-1}{2^{n+2}}}\equiv (-5)^{\frac{3^{2^n}-1}{2^{n+2}}}\pmod {2^{n+4}}$

Question: show that: $$3^{\frac{5^{2^n}-1}{2^{n+2}}}\equiv (-5)^{\frac{3^{2^n}-1}{2^{n+2}}}\pmod {2^{n+4}}$$ My idea: since I have prove $$5^{2^n}-1\equiv 0\pmod {2^{n+2}}$$ ...
0
votes
0answers
22 views

Proof of convergence of Kaprekar's Constant

I've tried googling this one a bit but nothing seems to come up, even though its considered to be a well known fact. Why does the kaprekar process of taking a 4 digit number: L, generating L' and L'' ...
0
votes
2answers
30 views

product of comprime numbers and UFD

It is well-known that if a product of coprime numbers is a perfect square, so are the numbers. The proof depends on fundamental theorem of arithmetic, and this implies that in a UFD, if ab is a ...
2
votes
2answers
28 views

Flip cards to get maximum sum

Given N cards where if ith card has number x on its front side then it will have -x on back side and a single operation that can be done only once that is to flip any number of cards in consecutive ...
15
votes
9answers
13k views

Efficient way to determine if a number is Perfect Square

Is there an efficient method to determine if a very large number (300 - 600 digits) is a perfect square without finding its square root. I tried finding the square root but I realized that even for ...
23
votes
1answer
340 views
+50

Evaluating the sum $\lim_{n\to \infty}\sqrt[2]{2+\sqrt[3]{2+\sqrt[4]{2+\cdots+\sqrt[n]{2}}}}$

The following nested radical $$\lim_{n\to \infty}\sqrt{2+\sqrt{2+\sqrt{2+\cdots}}}$$ is known to converge to 2. We can consider a similar nested radical where the degree of the radicals increases: ...
1
vote
1answer
39 views

Find extra work done by Bob

Alice has challenegd Bob game of N puzzle.N puzzle is played on N*N grid with each cell containing distinct numbered tile from 1 to N*N-1 Except one which is empty cell and represented as 0. Move ...
1
vote
0answers
25 views

variation of the Euler $\phi$ function?

Let $n \leq m$ be positive integers. Is there a function or expression giving the cardinality of the set $\{r \in \mathbb{Z}^+| 1 \leq r \leq m, \gcd(r,n) = 1 \}$? If $n = m$, it's just $\phi(n)$.
3
votes
0answers
91 views

Successive ratios of a sequence, is this limit true?

The natural numbers $1,2,3,4,5....$ can be calculated as the row sums of the triangle $T(n,k)$ equal to $1$ if $n \geq k$ and $0$ otherwise: $$\displaystyle T = \left(\begin{matrix} ...
6
votes
2answers
272 views

A series with only rational terms for $\ln \ln 2$

We all know that $$ \ln 2 = \sum_{n=1}^{\infty} \frac{(-1)^{n-1}}{n}. $$ Do you know a series with only rational terms for $$\ln \ln 2 = ?$$ Let's exclude base expansions with non ...
15
votes
3answers
331 views

Equality of Sums

I recently encountered the following equality ($\{\}$ denotes fractional part): $$\sum_{k=1}^{65}k\left\{\frac{8k}{65}\right\}=\sum_{k=1}^{65}k\left\{\frac{18k}{65}\right\}$$ and found it very ...
5
votes
2answers
56 views

minimal polynomial given an algebraic number

I am trying to find the minimal polynomial for the algebraic number $1+\sqrt{2}+\sqrt{3}$. My original thought was just let $\alpha=1+\sqrt{2}+\sqrt{3}$. The method I use though seems very ...
6
votes
2answers
126 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 ...
0
votes
2answers
64 views

how to find taxicab numbers but for squares?

Natural numbers that can be written as the sum of squares in two or more ways. The first ten numbers are 50, 65, 85, 125, 130, 145, 170, 185, 200, 205. $$ n = a^2 + b^2 = c^2 + d^2\\ a^2 − c^2 = d^2 ...
2
votes
0answers
84 views

“Remainder” operation in mod 2^32

I debated posting this here, in the cryptography SE, or the programming SE. Obviously, I chose here, but I'm not confident in my choice... I'm attempting to "undo" a function, but I've hit a slight ...
2
votes
3answers
31 views

If algebraic $a$ has degree $n$, so does $-a$

I feel like the best way to move forward is to use a contradiction proof. Since $a$ is algebraic, and is of degree $n$, it has a minimal polynomial of degree $n$, so we can write ...
3
votes
1answer
80 views

Last 7 digits of 7th powers

Alice and Bob play the following game. They alternately select distinct nonzero digits from $1$ to $9$, until they have chosen seven such digits. Consider the resulting seven-digit number by joining ...
6
votes
1answer
118 views

Can the product of $n$ factorials be $n$ factorial?

Are there any solutions to the equation $a_1!\cdot a_2!\cdots a_n!=n!$ with all variables being integers greater than or equal to $2$?
4
votes
1answer
83 views

Permutation Partition Counting

Consider the number $n!$ for some integer $n$ In how many ways can $n!$ be expressed as $$a_1!a_2!\cdots a_n!$$ for a string of smaller integers $a_1 \cdots a_n$ Let us declare this function as ...
20
votes
3answers
436 views
+100

Is this graph connected

Define the following equivalence relation $\sim$: We have $a \ \mathcal{R} \ b$ if and only if $a+b \ | \ ab-1$. $a \sim b$ if and only if there exist a sequence of integers $a_1, \ldots, a_n$ such ...
3
votes
4answers
108 views

Diophantine equation abc + abd + acd + bcd= 1

Is there a reference which classifies or at least gives an infinite family of integer solutions to the above equation? A solution to the problem would also be great obviously.
3
votes
2answers
36 views

explicit example of computing ray class field for imaginary quadratic?

Given an imaginary quadratic number field K, we can get its ray class field mod some ideal $\mathcal{m}$ by adjoining the j-invariant of an elliptic curve with complex multiplication given by ...
1
vote
2answers
200 views

Solutions to the Mordell Equation modulo $p$

It is well known that the Mordell Equation $x^2 = y^3 + k$ has finitely many solutions, but has solutions modulo $n$ for all $n$. One proof of this involves using the Weil Bound to show that $x^2 = ...
0
votes
2answers
105 views

Finding all possible pairs of integers $(a,b)$ such that $a^b=n$.

Given a large integer $n$ (could be as large as $10^{18}$), how can I find all possible pairs of integers $(a,b)$ such that $$a^b=n.$$ A fast algorithm is preferable. The question How to quickly ...
1
vote
2answers
67 views

Proving the divisibility of large numbers without making large calculations [duplicate]

How would you you show that $2^{32}+1$ is divisible by $641$ without making large calculations?
0
votes
0answers
27 views

general local to global principle

Consider the Diophantine equation $f(x)=0$, where x is a vector of integers and $f: \mathbb Z^n \rightarrow \mathbb Z$ is a polynomial function. Is the following statement true? The structure of the ...
3
votes
3answers
66 views

Prove that there exists $s$ such that $s(ab-1)^n +1$ is composite

I find this interesting question in a number theory book. Given two positive integers $a, b$ such that $a>1, b>1, \gcd(a, b)=1$. Prove that there exists a positive integer $s$ such that ...
4
votes
2answers
39 views

Proving Fibonacci inequality

I didn't see a question regarding this particular inequality, but I think that I have shown by induction that, for $n>1$. I am hoping someone can verify this proof. ...
0
votes
1answer
32 views

Find the number of positive integer $a \leq n$ such that $(a,n) = (a+1,n) = 1)

For every positive integer $n$, let $$A_n = \{a \in \mathbb{N} \mid 1 \leq a \leq n \mid gcd(a,n) = gcd(a+1, n) = 1\}$$ Evaluate $\mid A_n\mid$ Assume that $n$ has the factorization ...
0
votes
2answers
294 views

How many prime numbers exist all together in proportion to not prime numbers? [duplicate]

Q: If prime numbers are of infinitude, what is the proportion of not prime numbers to prime numbers? And if exist an infinitude of prime numbers, where are those not prime numbers? And what is an ...
29
votes
1answer
438 views

Very tight prime bounds

Is it possible that $$\left|\operatorname{li}(n)-\sum_{k=1}^{\lfloor\log(n)\rfloor}\dfrac{\pi(n^{1/k})}{k}-\log(2)-\dfrac{1}{2}\right|<\dfrac{2\sqrt{n}}{e\log(n)}?$$ Since $$ ...
2
votes
2answers
76 views

How prove $\frac{n^3-1}{mn-1}\equiv 1\pmod n$

let $m,n$ be positive integers $(m\ge n\ge 2)$ such that $$\dfrac{n^3-1}{mn-1}$$ is an integer. show that $$\dfrac{n^3-1}{mn-1}\equiv 1\pmod n$$ This problem is from this Ivan Loh solve this ...
0
votes
1answer
50 views

fastest algorithm for prime factorization [on hold]

I need the fastest algorithm to factorize the given number $N$ as a product of primes. $$N=p_1^{e_1}p_2{e_2}\ldots p_n^{e_n}$$ where $p_1, p_2,\ldots ,p_n$ are primes and $e_1,e_2,\ldots, e_n$ are ...
1
vote
2answers
45 views

Help with proof regarding degrees of polynomials

How do you prove that if $f(x)\mid g(x)$ in $F[x]$, then either $g(x) = 0$ or $\deg(g(x)) \geq \deg(f(x))$ I'm not really sure how to prove these types of statements
1
vote
0answers
24 views

Mobius function verification

I am looking to verify my answer to the question $$F(n)=\sum_{d|n}{\mu(d)\sigma(d)}=(-1)^{\omega(n)}\prod_{j=1}^{\omega(n)}{p_j}$$ Where $\mu$ is the Mobius function, $\sigma$ is the sum of divisors ...
-1
votes
0answers
39 views

How does this method work? [on hold]

Let $n=16$ for an example: step 1: get set of prims from $1$ to $\sqrt{2n}: \{2, 3, 5\}$, step 2: get set of $n \mod 2, n \mod 3, n \mod 5: \{0, 1, 1\}$, setp 3: from $0$ to $n-3$, ...
0
votes
1answer
246 views

How to use the method of “Hensel lifting” to solve $x^2 + x -1 \equiv 0\pmod {11^4}$?

I got $x^2 + x + 10 \equiv 0\pmod {11}$ I am confused about using the Hensel lifting method. Can someone just help me out with that please.
1
vote
2answers
41 views

Diophantine solution to a fraction

How can we find solutions to the following equation: $$ y=\dfrac{x^2-1085}{14718-2x}$$ where $x,\ y$ are integers.
1
vote
1answer
53 views

Contracted ideals in number fields

I am trying to translate a section of Wolfgang Krull's report "Idealtheorie". At one point (Section $7$ on Quotient Rings) I believe that he makes something like the following statement: Suppose for ...
1
vote
1answer
26 views

Sizes of Blocks of Consecutive Integers Divisible by at Least One Prime Less than or Equal to $r$.

Let $f(r)$ be the largest integer such that there exists a block of $f(r)$ consecutive integers each divisible by some prime that is less than or equal to $r$. For example, $f(2)=1$ because it is ...
7
votes
2answers
256 views

Is $7^{8}+8^{9}+9^{7}+1$ a prime? (no computer usage allowed)

Prove or disprove that $$7^{8}+8^{9}+9^{7}+1$$ is a prime number, without using a computer. I tried to transform $n^{n+1}+(n+1)^{n+2}+(n+2)^{n}+1$, unsuccessfully, no useful conclusion.