Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

33
votes
0answers
570 views

On Ramanujan's curious equality for $\sqrt{2\,(1-3^{-2})(1-7^{-2})(1-11^{-2})\cdots} $

In Ramanujan's Notebooks, Vol IV, p.20, there is the rather curious, $$\sqrt{2\,\Big(1-\frac{1}{3^2}\Big) \Big(1-\frac{1}{7^2}\Big)\Big(1-\frac{1}{11^2}\Big)\Big(1-\frac{1}{19^2}\Big)} = \Big(1+\frac{...
31
votes
0answers
789 views

How to solve this two simultaneous “divisibilities” : $n+1\mid m^2+1$ and $m+1\mid n^2+1$

Is it possible to find all integers $m>0$ and $n>0$ such that $n+1\mid m^2+1$ and $m+1\,|\,n^2+1$ ? I succeed to prove there is an infinite number of solutions, but I can not progress anymore......
21
votes
0answers
195 views

$x_1 = 2$, $x_{n + 1} = {{x_n(x_n + 1)}\over2}$, what can we say bout $x_n \text{ mod }2$?

Let$$x_1 = 2, \quad x_{n + 1} = {{x_n(x_n + 1)}\over2}.$$What can we say about the behavior of $x_n \text{ mod }2$? Is there an exact formula for $x_n \text{ mod }2$?
18
votes
0answers
251 views

Finding primes so that $x^p+y^p=z^p$ is unsolvable in the p-adic units

On my number theory exam yesterday, we had the following interesting problem related to Fermat's last theorem: Suppose $p>2$ is a prime. Show that $x^p+y^p=z^p$ has a solution in $\mathbb{Z}_p^{\...
18
votes
0answers
760 views

Are there unique solutions for $n=\sum_{j=1}^{g(k)} a_j^k$?

Edward Waring, asks whether for every natural number $n$ there exists an associated positive integer s such that every natural number is the sum of at most $s$ $k$th powers of natural numbers (...
17
votes
0answers
215 views

Where Fermat's last theorem fails

It's fairly well known that Fermat's last theorem fails in $\mathbb{Z}/p\mathbb{Z}$. Schur discovered this while he was trying to prove the conjecture on $\mathbb{N}$, and the proof is an application ...
17
votes
0answers
422 views

A question about the divisibility of sum of 2 consecutive primes.

Well as I was curious about the sum of $2$ consecutive primes, after proving that the sum for the odd primes always has at least 3 prime divisors, I came up with this question: Find the least ...
12
votes
0answers
317 views

Are all totient values of Fibonacci Numbers distinct?

This question was inspired while I was seeing how certain recurrence relations would behave when I applied Multiplative Functions. Let $F_{n}$ be a sequence for which $F_{1}=1,F_{2}=1$, and $F_{n}=...
12
votes
0answers
271 views

Dividing the whole into a minimal amount of parts to equally distribute it between different groups.

Suppose we have a finite amount of numbers $x_1, x_2, ..., x_n$ ($x_i\in\mathbb{N}$) and an object that should be divided into parts in such a way that it can be without further dividing distributed ...
12
votes
0answers
599 views

How does a Lehmer Sieve work?

http://en.wikipedia.org/wiki/Lehmer_sieve Apparently a Lehmer Sieve was a mechanical device that used chains and pulleys to factor numbers and solve diophantine equations. It once was able to factor $...
11
votes
0answers
253 views

An infinitude of “congruence condition” primes?

Background: Several special classes of primes can be written as primes that satisfy some additional constraint $f(p)\equiv 0\pmod p$; for instance, Wilson primes are congruence primes with $f(p)=\...
11
votes
0answers
625 views

Understanding Ramanujan's approach in his proof of Bertrand's Postulate

I've been reading through Ramanujan's proof of Betrand's Postulate and I'm not clear why he didn't state his proof in terms of $\varphi(2x) - \varphi(x)$ What would be wrong with this approach for ...
10
votes
0answers
356 views

Power Diophantine equation involving primes: $(p+q)^q-p^q-q^q+1=n^{p-q}$

Suppose $p$ and $q$ are prime numbers, and $n>1$ is a positive integer. Find all solutions to the following Diophantine equation:$$(p+q)^q-p^q-q^q+1=n^{p-q}$$ What I have tried: Obviously $p>q$...
10
votes
0answers
112 views

Is there a clever way to find a smaller number that produces the Euclidean algorithm of given length?

Is there a simple way to tell if for a given $n$ there is $m$ such that the Euclidean algorithm on $n,m$ runs for a given number of steps, and/or a way to find $m$ efficiently (other than testing all $...
10
votes
0answers
224 views

Number of ways to express a binary number in a certain way

So I'm working on a problem where I get to a point where I have to count the number of solutions to an equation or at least find a decent upper bound to be used in an estimate I need later. The ...
10
votes
0answers
874 views

How many integer solutions to a diophantine equation

Starting with the equation: $\frac{1}{a}+\frac{1}{b}=\frac{p}{10^n}$, I reached the equation: $10^{n-log(p)} = \frac{ab}{a+b}$. Now given the positive integer $n$, for what integer values of $p$ ...
9
votes
0answers
52 views

What to keep in mind when attempting proof of basic properties of divisibility/what techniques are useful/what's the intuition for showing them?

So I am currently trying to prove some basic divsiibility relations, as follows. If $a \mid b$ and $a \mid c$, then $a \mid (b + c)$. If $a \mid b$ and $s \in \mathbb{Z}$, then $a \mid sb$. ...
9
votes
0answers
92 views

Integer polynomials with roots in every $\mathbb{Z}_p$ but no rational roots.

I want to find polynomials in $\mathbb{Z}[x]$ with degree as small as possible such that these polynomials have no rational roots but have a root in the $p$-adic integers $\mathbb{Z}_p$ for every ...
9
votes
0answers
199 views

If $b$ is even and not a power of two, can $b^4+1$ be a weak pseudoprime?

The complete question is already in the title but we shall provide some motivation as well. We study generalized Fermat numbers defined by: $$\mathrm{GF}(n,b) = b^{2^n}+1$$ where $b$ and $n$ are ...
9
votes
0answers
205 views

Let $p$=prime and $\sqrt{x}+\sqrt{y}<\sqrt{2p}$

Let $p$ be a fixed odd prime. Let $x,y\in \mathbb{Z}_+$ such that $\sqrt{x}+\sqrt{y}<\sqrt{2p}$. Prove that $$\sqrt{x}+\sqrt{y}\le \sqrt{\frac{p-1}{2}}+\sqrt{\frac{p+1}{2}}.$$ Any ideas at all? ...
9
votes
0answers
242 views

when $F_n^2+F_m^2$ is a square for fibonacci numbers

This is a curiosity question I'm trying to solve a Diophantine equation and I need some results about fibonnacci numbers, I encountered this problem: For which couple of integers $(n,m)$ the ...
9
votes
0answers
249 views

Olympiad-style question about functions satisfying condition $f(f(f(n))) = f(n+1) + 1$

QN: What functions (from non-negative integers to non-negative integers) satisfy the condition $$f(f(f(n))) = f(n+1) + 1$$ Comment: Evidently $f(n) = n+ 1$ is one solution. Equally evidently no ...
9
votes
0answers
153 views

Proving that $\sigma_7(n) = \sigma_3(n) + 120 \sum_{m=1}^{n-1} \sigma_3(m)\sigma_3(n-m)$ without using modular forms?

This problem appears as a (starred!) exercise in D. Zagier's notes on modular forms. I have to admit that I have no idea how to do it. Here, $\sigma_k(n) =\sum_{d\mid n} d^k$, as usual. This ...
9
votes
0answers
142 views

Which digit occurs most often?

Is there any method to calculate, which digit occurs most often in the number $$4 \uparrow \uparrow \uparrow \uparrow 4\ ,$$ the fourth Ackermann-number ? Or would it be necessary to calculate the ...
9
votes
0answers
432 views

Prove that Bezout's coefficients given by the extended Euclidean algorithm are minimal in absolute value

Bezout's lemma states that if a and b are integers, and at least one of them is non-zero, then there exist integers $x, y$ such that $$ax + by = gcd(a, b)$$ One way of finding such a pair $(x, y)$ 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$...
8
votes
0answers
91 views

Greedy algorithm Egyptian fractions for irrational numbers - patterns and irrationality proofs

This is related to another question on this site, but it's not a duplicate, because the actual questions I ask are completely different. In one of the answers Jeffrey Shallit provided a very useful ...
8
votes
0answers
52 views

Intuition behind the proof of the validity of the Euclidean algorithm

As the question title suggests, could anybody explain to me their intuition behind the proof of the validity of the Euclidean algorithm?
8
votes
0answers
246 views

Positive integers $a,b$ satisfying $a^3+a+1=3^b$

How to prove that $a=b=1$ is the only positive integer solution to the following Diophantine equation?$$a^3+a+1=3^b$$
8
votes
0answers
75 views

Two algebraic number theory questions.

I have two algebraic number theory questions. See page 26 here, specifically Lemma 5.11. Lemma 5.11. The group $\mathcal{O}^\times$ is generated by roots of unity and $[\mathcal{O}^\times]^+$, the ...
8
votes
0answers
215 views

What is known about the sum $\sum\frac1{p^p}$ of reciprocals of primes raised to themselves?

Consider the following series: $$\sum_{p\in\mathcal{P}}\frac{1}{p^p}$$ where $\mathcal{P}$ is the set of all prime numbers: $\mathcal{P}=\{2,3,5,7,11,13,\ldots\}$. My question is: Is this a ...
8
votes
0answers
192 views

Is there some exact form of $n$ for the number of $(i,j,k)$ satisfying $ijk = (n-i)(n-j)(n-k)$

For any positive integer $n$, $i,j,k$ are also positive integers, and $0 <i,j,k < n$. How many solutions of the form $(i,j,k)$ are there for the equation $ijk = (n-i)(n-j)(n-k)$?
8
votes
0answers
211 views

How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes?

Is there an easy way to compute the following question: How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes? The only thing that ...
7
votes
0answers
190 views

When is the polynomial $\prod\limits_{i=1}^n\,\left(x-a_i\right)+1$ reducible in $\mathbb{Z}[x]$?

This post is inspired by Prove that the polynomial $\prod\limits_{i=1}^n\,\left(x-a_i\right)-1$ is irreducible in $\mathbb{Z}[x]$.. (A) Find all positive integers $n$ and integers $a_1,a_2,\...
7
votes
0answers
84 views

Does anyone know a reference to best-fitting lines with integral coefficients?

I'm writing up a manual on how to generate "nice" Linear Algebra problems; that is, where the solutions tend to be integral. I "discovered" the following fact about the best-fitting line: Theorem. ...
7
votes
0answers
218 views

Basic Olympiad number theory problem about prime numbers

I'm learning a basic lesson of number theory and get stuck with this : Find all positive integers $n$ and prime numbers $p$ such that $n^p+3^p$ is a perfect square. I found that if $p \ge 3$, then $...
7
votes
0answers
77 views

Can all natural numbers be represented as palindromes in some base $b$?

$1$ can be represented as a palindrome in any base, as can $2$ in any base greater than $2$. In general, all numbers can be written as a palindrome in any base greater than the number, but this is ...
7
votes
0answers
158 views

Is the Euler function $\phi$ constant in arbitrarily large intervals?

Is it true that for every $k \in \mathbb{N}$ there exists a natural number $x$ such that $\phi(x)=\phi(x+1)=\cdots=\phi(x+k)$, where $\phi$ is the Euler's totient function? I thought about this ...
7
votes
0answers
132 views

An Impossible Sequence of Prime Powers

Let $x_1,x_2,\ldots$ be a sequence of positive integers that satisfies the recurrence relation $$x_{n+1}=2x_n(x_n-1)+1$$ for all positive integers $n$. It seems impossible that every term in this ...
7
votes
0answers
135 views

Looking for all sequences such that $a_i^2+a_j^2=a_k^2+a_l^2$ whenever $i^2+j^2=k^2+l^2$

I'm working in a difficult functional equation, and I have reduced the problem to the following question ($\mathbb{N}$ denotes the set of non negative integers $0,1,2,3,4\cdots$) Question: Can we ...
7
votes
0answers
81 views

Integers neither as sum nor difference of perfect powers

Are there infinitely many positive integers $n$ for which there do not exist integers $a,b\geq 1$ and $c,d\geq 2$ such that $n=a^c+b^d$ or $n=a^c-b^d$? [Source: Hungarian competition problem]
7
votes
0answers
178 views

Infinite sum involving $q$-adic representations of whole numbers and $q$-factorial numbers

Let $q \in \mathbb{N}_{\geq 2}$. For $n \in \mathbb{N}_0$, let $$\mathrm{fac}_q(n) := \prod_{i=1}^n (1+q+\dots+q^{i-1}) = \prod_{i=1}^n \frac{q^i-1}{q-1}$$ be the $q$-factorial of $n$. In particular, ...
7
votes
0answers
135 views

What is the Gauss sum equivalent of $\Gamma(s+1) = s\Gamma(s)$?

Gauss sums are analogous to the Gamma function: fix a complex number $s$ with real part $>0$. Then we have a multiplicative character $\chi_s :\mathbf R^{\times}_{>0} \to \mathbf C^\times$ given ...
7
votes
0answers
373 views

A conjecture about mersenne primes and non-primes

Latest Edit: My hypothesis is simply that A056295(n) are spread around some smooth curve and higher than the curve if M(n) is a non-prime (and perhaps also even higher yet if M(n) has many factors ...
6
votes
0answers
92 views

Is a finite number of quadratic equations in two variables sufficient to solve for the two variables?

Let's say I’m trying to solve a Diophantine problem in two positive integers, $y$ and $q$. Furthermore, let’s say I can derive an extremely large (read: arbitrary) number of equations of the form $$ay^...
6
votes
0answers
79 views

Is there a finite list of identites in the language of $(\mathbb{N},0,1,+,\times,\mathrm{gcd},\mathrm{lcm})$ that generates all the others?

Let $\Phi$ denote the set of all identities satisfied by $(\mathbb{N},0,1,+,\times,\mathrm{gcd},\mathrm{lcm}).$ Question. Is $\Phi$ finitely axiomatizable? If so, I'd like to see a list of ...
6
votes
0answers
71 views

Making perfect cube from factors of $20!$

At least how many different factors of $20!$ must we choose so that we can always find some subset whose product is a perfect cube? For example, if we choose $\{2,3,5,7,11,13,17,19,22,26,34,38\}$, ...
6
votes
0answers
62 views

The Greatest Common Divisor of All Numbers of the Form $n^a-n^b$

For fixed nonnegative integers $a$ and $b$ such that $a>b$, let $$g(a,b):=\underset{n\in\mathbb{Z}}{\gcd}\,\left(n^a-n^b\right)\,.$$ Here, $0^0$ is defined to be $1$. (Technically, we can also ...
6
votes
0answers
80 views

Integer divisibility

Given a (not strictly) decreasing sequence of natural positive numbers $a_1, a_2, \dots, a_n$ prove that $$ \prod_{i<j} j-i \quad\big|\quad \prod_{i<j} a_i - a_j - i +j $$ I already know a ...
6
votes
0answers
65 views

Divisibility sequence resulting in limit with pi

Consider the following sequence of operations : Start with a natural number $n$ and then round it up to the closest multiple of $n-1$ .Then round up this new number to the closest multiple of $n-...