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

learn more… | top users | synonyms (1)

29
votes
0answers
409 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)} = ...
25
votes
0answers
633 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 ...
18
votes
0answers
746 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 ...
16
votes
0answers
158 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 ...
15
votes
0answers
405 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
568 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
310 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 ...
11
votes
0answers
256 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 ...
11
votes
0answers
376 views

If $p$, $q$ are naturals, solve $p^3-q^5=(p+q)^2$.

In If $p,q$ are prime, solve $p^3-q^5=(p+q)^2$., the author asks to solve the equation $p^3-q^5=(p+q)^2$ for primes $p$ and $q$. A proof is given that $p=7, q=3$ is the only solution. In this ...
11
votes
0answers
246 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 ...
11
votes
0answers
606 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
118 views

Arrange Relatively Prime Numbers in a Circle

The question: In how many ways can you arrange the numbers $1$ to $8$ in a circle so that neighboring numbers are relatively prime? Can you generalize for $1$ to $n$? It's fairly easy to list ...
10
votes
0answers
851 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
194 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
194 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
233 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
216 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 ...
9
votes
0answers
289 views

A question on odd perfect numbers

Let $\sigma(x)$ be the sum of the divisors of the positive integer $x$. If $\sigma(M) = 2M$, then $M$ is said to be perfect. Currently, there are $48$ known examples of even perfect numbers -- on ...
9
votes
0answers
148 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
135 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
406 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
191 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
209 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
67 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 ...
7
votes
0answers
204 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
74 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
152 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
198 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 ...
7
votes
0answers
125 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
132 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
222 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 ...
7
votes
0answers
75 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
174 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
366 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
63 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 ...
6
votes
0answers
82 views

Sequence involving floor function - limit and bounds

My first time here, so please excuse any breaches of etiquette. For a given $p \in \mathbb N$ and irrational $\alpha$, let $\varepsilon_n=\alpha n-\lfloor \alpha n \rfloor,$ and ...
6
votes
0answers
127 views

A bound on the nth prime.

Is there any combinatorial argument to show that the nth prime $p_n = \mathcal{O}(n^k)$ for fixed $k$ ? There is a problem in the book by Apostol to find upper bounds on $p_n$, the Prime Number ...
6
votes
0answers
215 views

Does the set of $m \in Max(ord_n(k))$ for every $n$ without primitive roots contain a pair of primes $p_1+p_2=n$?

I have made the following observation: for those n even numbers that do not have primitive roots modulo n ,$Pr(n)$, the set $M(n)$ of those $k$ having a maximum multiplicative order $ord_n(k)$ ...
6
votes
0answers
160 views

Olympic number theory problem: is this solution fine and sufficiently well written?

Determine all the positive integers $m$ such that both the ratios $$ \frac{2(5^m+5)}{3^m+1}, \frac{9^m+1}{5^m+5}$$ are integers. Attempt to a solution: If the ratios are both integers, than their ...
6
votes
0answers
551 views

2015-related question: why are Lucas-Carmichael numbers named after Lucas?

Summary 2015 is a so called Lucas-Carmichael number. I believe (for reasons that I will explain below) that the 'Carmichael' in the name is a reference to ordinary Carmichael numbers and not to the ...
6
votes
0answers
142 views

What is known about the solutions to $\varphi(a)+\varphi(b)=\varphi(a+b)$?

As of late I have been researching Euler's Totient function. For the last week or so I have specifically been studying the equation: $\varphi(a)+\varphi(b)=\varphi(a+b)$ While the equation ...
6
votes
0answers
47 views

Inverse image of rationals under tangent function is free abelian?

It is easy to see that the set $\{x:\tan x\in \Bbb Q \,\, or\,\, \pm\infty\}$ forms a group under addition. It is a free abelian group?
6
votes
0answers
87 views

Does there exist a positive $k$ s.t. for all $r\geq k$, “$\sigma_r(m)<\sigma_r(n)$ for every $m<n$” for infinitely many odd positive integers $n$?

Does there exist a positive real $k$ such that for all real $r\geq k$, "$\sigma_r(m)<\sigma_r(n)$ for every $m<n$" for infinitely many odd positive integers $n$? $\sigma_r(n)$ is the sum of the ...
6
votes
0answers
375 views

number of quadratic residues modulo n

Define $f(n)$ to be the number of quadratic residues modulo $n$. I would like to show that $f$ is multiplicative, that is, for any positive integers $m,n > 1$, $f(mn) = f(m)f(n)$ whenever $(m,n) = ...
6
votes
0answers
159 views

Twin Prime Powers

What are all the possible triplets of numbers $a$, $b$, $c$ such that $a+2=b$, $a+4=c$, and all $3$ are prime powers (where one must be a power of $3$)? I'm aware of the cases for when they are ...
6
votes
0answers
131 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 ...
6
votes
0answers
110 views

Determine the least prime $p$ for which $2^{p-1} \equiv 1 \pmod {p^2}$.

Determine the least prime $p$ for which $2^{p-1} \equiv 1 \pmod {p^{2}}$ .
5
votes
0answers
94 views

Looking for the most elementary proof that $48X^4+12X^2+1=Y^2$ has no non-trivial integer solution.

As relayed in this question of mine (which is more general in scope), I believe I have found a relatively easy, and completely elementary, way to show that the equation $$48X^4 + 12X^2+1 = Y^2$$ has ...
5
votes
0answers
57 views

proof - Bézout Coefficients are always relatively prime

I had been researching over the Extended Euclidean Algorithm when I happened to observe that the Bézout Coefficients were always relatively prime. Let $a$ and $b$ be two integers and $d$ their GCD. ...
5
votes
0answers
60 views

Smallest $n$-digit number $x$ with cyclic permutations multiples of $1989$

Suppose $x=a_1...a_n$, where $a_1...a_n$ are the digits in decimal of $x$ and $x$ is a positive integer. We define $x_1=x$, $x_2=a_na_1...a_{n-1}$, and so on until $x_n=a_2...a_na_1$. Find the ...