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

learn more… | top users | synonyms (1)

29
votes
0answers
1k views

A very nice divisibility problem

I have a very hard problem: Prove that, if $2^{2^j} a + 1$ divides $c^{2^j}+1$ for fixed integers $a,c$ and all nonnegative integers $j$, then $a=1$ and $c=2^l$ for some odd positive integer $l$, ...
15
votes
0answers
729 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 ...
12
votes
0answers
146 views

Partition of ${1, 2, … , n}$ into subsets with equal sums.

The following is one of the old contest problems (22nd All Soviet Union Math Contest, 1988). Let $m, n, k$ be positive integers such that $m \ge n$ and $1 + 2 + ... + n = mk$. Prove that the numbers ...
12
votes
0answers
516 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
369 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 ...
10
votes
0answers
230 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 ...
10
votes
0answers
239 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 ...
10
votes
0answers
593 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 ...
9
votes
0answers
330 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 ...
9
votes
0answers
834 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$ ...
8
votes
0answers
106 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 ...
8
votes
0answers
184 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? ...
8
votes
0answers
223 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 ...
8
votes
0answers
119 views

Given the first $n$ primes, find the least common multiple of $p_1 - 1$, $p_2 - 1$, …, $p_n - 1$

Given the first $n$ primes, we can label the $k$th prime as $p_k$. So, what is the least common multiple(LCM) of {$p_1 - 1$, $p_2 - 1$, $p_3 - 1$, ..., $p_n-1$}? In other words, if we subtract $1$ ...
8
votes
0answers
272 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 ...
8
votes
0answers
139 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 ...
8
votes
0answers
126 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 ...
8
votes
0answers
190 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
206 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
199 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
64 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
145 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
189 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
122 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
123 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
212 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
208 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 ...
7
votes
0answers
73 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
171 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
378 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 ...
7
votes
0answers
361 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
59 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 ...
6
votes
0answers
59 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
73 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
118 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
210 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
155 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
537 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
136 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
46 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
85 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
358 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
128 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
104 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
58 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 ...
5
votes
0answers
166 views

Alternative Proof of $\sqrt{2}$ is irrational

Can anyone check if this proof is correct. Thank you. Proof that $\sqrt{2}$ is irrational. Let x = $\sqrt{2}$ then $x^2=2$ and $x^2-2=0$ By the Rational Root Theorem, we have: the number $1$ ...
5
votes
0answers
127 views

Sum of like powers equal to a power

It's not hard to prove that $$(1+2+3+\ldots+n)^2=1^3+2^3+\ldots+n^3$$ ( for example using induction ) A generalization of this is also known : $$(\sum_{d \mid n} \tau(d))^2=\sum_{d \mid n} ...
5
votes
0answers
48 views

About the sum $ s_n:=\sum_{k=1}^{n} \text{lcm}(k,n) $

I'm currently studying the following sum: $$ s_n:=\sum_{k=1}^{n} \text{lcm}(k,n) $$ I manipulated it as follows: $$\begin{align} s_n&=\sum_{k=1}^{n} \text{lcm}(k,n)\\ ...
5
votes
0answers
111 views

When $\frac{1}{n}\binom{n}{r}$ is an integer , again?

This question follows a previous one If $n$ and $r$ are coprime then $a_{n,r}=\frac{1}{n}\binom{n}{r}$ is integer but this is not a necessary condition. Question: what is a necessary and ...