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

learn more… | top users | synonyms

64
votes
0answers
4k views

A variation of Fermat's little theorem

Fermat's little theorem states that for $n$ prime, $$ a^n \equiv a \pmod{n}. $$ The values of $n$ for which this holds are the primes and the Carmichael numbers. If we modify the congruence ...
15
votes
0answers
275 views

Is there any integer solutions of $3x^3+3x+7=y^3$?

$3x^3+3x+7=y^3$ $x, y \in \mathbb{N}$ Having thought about it two hours, and I'm still not sure how to show there actually aren't any integer solutions. EDIT Another formulation of this problem: ...
15
votes
0answers
569 views

A very nice divisibility problem

A very hard problem, here it is: 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 ...
12
votes
0answers
199 views

How to find all functions $f$ such that $f(a)+f(b)$ is square number, if $a+b$ is square number.

Question: For any $a,b\in N^{+}$, if $a+b$ is square number, then $f(a)+f(b)$ is also a square number. Find all such functions. My try: It is clear that the function $$f(x)=x$$ satisfies the ...
12
votes
0answers
597 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 ...
11
votes
0answers
219 views

When is $(x^n-1)/(x-1)$ a prime number?

Let $x > 1$ and let $n$ be a prime. I'm wondering if a characterization of this is known. That is, what are sufficient and necessary conditions for $$ \dfrac{x^n-1}{x-1} = 1 + x + x^2 + \cdots + ...
11
votes
0answers
152 views

Peculiar numbers

This is from the weekly math challenge of the French newspaper Le Monde. "Magical" numbers have a remarkable property: when one of them, say $n$, is squared, it is such that $n^2$ ends with $n$. ...
9
votes
0answers
237 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 ...
9
votes
0answers
293 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 ...
9
votes
0answers
184 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 ...
9
votes
0answers
653 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
41 views

Dividing first $n$ primes into two sets with equal sum

Let $N$ be a positive integer. Does there always exist $n>N$ such that the first $n$ primes can be divided into two sets with equal sum? If $n$ is even, the sum of the first $n$ primes is odd, so ...
8
votes
0answers
135 views

Show that $x$ is rational.

Sincerely, I don't have the slightest idea for this one : Suppose that $a,b$ are distinct positive integers and that the numbers $\lfloor a^n x\rfloor $ with $n\in\Bbb{N}$ and $x$ a fixed real ...
8
votes
0answers
448 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 ...
8
votes
0answers
169 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
187 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
33 views

Divisors of sequence $n,P(n),P(P(n)),\ldots$

Let $P(x)$ be a polynomial with nonnegative integer coefficients consisting of more than one nonzero term. Let $n$ be a positive integer. Is the set of prime numbers which divide at least one number ...
7
votes
0answers
85 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$ ...
7
votes
0answers
166 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
140 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
100 views

Find all integer solutions of the equation

Find all integer solutions to $3^a+7=2\cdot5^b$. Basically I've tried almost every tool I know of NT (Zsigmondy,LTE,reducing to various modulus) but nothing worked. So far I just know that (1,1) ...
7
votes
0answers
111 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 ...
7
votes
0answers
87 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 ...
7
votes
0answers
161 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 $x^3-y^5=(x+y)^2$ for primes $p$ and $q$. A proof is given that $p=7, q=3$ is the only solution. In this ...
7
votes
0answers
226 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 ...
6
votes
0answers
59 views

When can $n^k+k$ be a perfect square?

For what positive integers $k$ does there exist a positive integer $n$ such that $n^k+k$ is a perfect square? Certainly for all $k$ such that $k+1$ is a perfect square, since we can substitute $n=1$. ...
6
votes
0answers
94 views

Books to read to understand Terence Tao's Analytic Number Theory Papers

I tried to understand Terence Tao's Analytic Number Theory Papers. For example, this paper, Every Odd Number Greater Than 1 is The Sum of at Most Five Primes. Which books shall I read to prepare ...
6
votes
0answers
171 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
6
votes
0answers
40 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
78 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
217 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
130 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
110 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
312 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
213 views

Diophantine special problem

This is my another question on Diophantine equations. Prove the following great and special problem. Let $D$ and $k$ be positive integers and $p$ be a prime number such that $gcd(D, kp) = 1$. Prove ...
6
votes
0answers
334 views

On the equation $m^3-m^2+1 = n^2$

(i) How can I find all positive integers $m$ such that $m\equiv 4 \pmod 7$ and $m^3-m^2+1$ is a perfect square? (ii) Is there a method to solve this equation over positive integers: $$m^3-m^2+1 = ...
5
votes
0answers
32 views

Congruence properties of $a^5+b^5+c^5+d^5+e^5=0$?

It is known that given a solution to, $$a^4+b^4+c^4 = d^4\tag1$$ then either $-c+d,\;c+d$ is always divisible by $2^{10}$. For example, $$95800^4+414560^4+217519^4=422481^4$$ then ...
5
votes
0answers
43 views

If $a$ is a quadratic residue modulo every prime $p$, it is a square - without using quadratic reciprocity.

The question is basically the title itself. It is easy to prove using quadratic reciprocity that non squares are non residues for some prime $p$. I would like to make use of this fact in a proof of ...
5
votes
0answers
46 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]
5
votes
0answers
123 views

Diophantine: $x^3+5=y^5$

Find all integers $x$ and $y$ such that $x^3+5=y^5$. I found this after solving the equation $3^a+5=2^b$. For this equation, since $(a,b)=(3,5)$ is a solution, it is possible to write it as ...
5
votes
0answers
165 views

$(b-a)^2-2ab$ is a perfect square.

I'm in need of some help if possible, about a formula, theorems, old works, ideas, or even an existing solution are welcome. The problem is that i have two distinct natural numbers as $b > a > ...
5
votes
0answers
89 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 ...
5
votes
0answers
90 views

What should be taught about the reciprocity law for high school gifted student

This autumn I have to teach a mini course for a small group of high school student (mathematical gifted class) on Quadratic Reciprocity Law (3 lectures in ten hours). This is the requirement of the ...
5
votes
0answers
169 views

How to partition $S$ in this way?

Assume: $$ P =\{p_1,p_2,\cdots,p_K\}\subset \{1,2,\dots,N\},\quad |P| = K, \qquad x \in \mathbb{R}_+^K , \qquad w = e^{-j\frac{2\pi}N} $$ and, $$ f(l) = \sum_{i=1}^K \sum_{j=1}^K x_i x_j ...
5
votes
0answers
247 views

Maximum length of sequence of non-coprimes of $N$ - least upper bound for Jacobsthal's function

I am looking at the length of the longest sequences of adjacent integers that are not coprime to $N$ for very large $N$. Let $F_N$ be the set of integers less than $N$ which are not coprime with $N$: ...
5
votes
0answers
125 views

Best upper bound on the number of divisors of $n$ that are larger than $N$.

I am looking for the best upper bound on $$\sum_{\substack{d | n\\ d \geq N}} 1.$$ I know that $$ d(n) = \sum_{\substack{d | n}} 1 \leq e^{O(\frac{\log n}{\log \log n})}. $$ For my application, I ...
5
votes
0answers
121 views

divisibility by powers of $2$ of diagonal sums of infinite latin square

This array is formed by placing integers such that each is the smallest such that the rectangle with it and the top left hand corner as opposite corners does not contain the same integer twice in any ...
5
votes
0answers
191 views

Carmichael number factoring

The task I'm faced with is to implement a poly-time algorithm that finds a nontrivial factor of a Carmichael number. Many resources on the web state that this is easy, however without further ...
5
votes
0answers
85 views

Integer weights used to cover all numbers from 1 to N with redundancies in case of breakage

Bachet's Problem (arxiv) is a famous problem where we have to find the smallest set of positive integers such that they measure every number between 1 and 40. This can be generalized to every integer ...
5
votes
0answers
390 views

Digital Numbers using all digits from 1-9

Call a number a digital number if it consists of all the digits from 1-9, each used exactly once. What is the probability that a digital number will be divisible by 7 ? What is the probability that a ...