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

learn more… | top users | synonyms (1)

4
votes
3answers
244 views

Does the sequence $q(n)=3n+1+\frac{1-(-1)^n}{2}$ generate all the prime numbers?

Define $$q(n)=3n+1+\frac{1-(-1)^n}{2} \quad, \quad n\in \mathbb N.$$ $$1,5,7,11,13,17,19,23,25,29,31,35,\dots$$ It seems like this formula gives all primes $>3$ (although not just primes of ...
0
votes
1answer
39 views

Taking averages of averages

The numbers $1000$ and $1000000$ are already written on a paper. We are allowed to write down an average of two written numbers, if that average is an integer has not been written before, and we can ...
3
votes
2answers
30 views

For which $0\leq a<p^2$, where $p$ is an odd prime, we have that $(2p-1)!\equiv a\mod{p^2}$

Let $p$ be an odd prime. I need to find for which $0\leq a < p^2$, $(2p-1)!\equiv a\mod{p^2}$. If $a\equiv (2p-1)!\mod{p^2}$, then we have that $a = kp^2 + (2p-1)!$, and therefore $p\mid a$, ...
2
votes
1answer
81 views

Discrete logarithm modulo powers of a small prime

Is there an efficient way to compute $x$ in $2^x \equiv b \pmod {p^m}$, where $p$ is a small odd prime and $m$ could be a large integer? I know the solution is of the form $x=\phi(p^m) k + y$ for ...
0
votes
0answers
27 views

Sum of fractional parts in $(1,2)$

Let $a,b,c$ be any rational, non-integer positive numbers with non-integer sum. Does there always exist a positive integer $k$ such that $ka,kb,kc$ are not integers and $\{ka\}+\{kb\}+\{kc\}\in(1,2)$? ...
1
vote
1answer
19 views

Return a cross product of two sets A and B such that only one entry is returned based on a condition

Lets say I have a set $A={\text{'Akshat'},\text{'John'},\text{'Mike'}}$ and a set $B={\text{'Modi'},\text{'Kerry'}}$. Set $A$ represents a set of voters while $B$ represents a set of candidates for an ...
0
votes
3answers
68 views

Find the number of sums that you will get A, when A=100?

Problem: Take any number $A \in \Bbb{N} = \{1, 2, 3, \dots\}$, and then take $x, y \in \Bbb{N}$, where $x \ne y$ and $x + y = A$. Find the number of possible choices for $x$ and $y$ when $A=100$. ...
3
votes
3answers
42 views

Show that for $x,y,z\in\mathbb{Z}$, if $x$ and $y$ are coprime, then $\exists n\in\mathbb{Z}$ such that $z$ and $y+xn$ are coprime.

Not sure where to start on this one. I understand that coprime indicates that their GCD is 1, but I am somewhat confused how to proceed.
2
votes
0answers
24 views

On some iterated inequalities and $x \geq 5$

Let $x \in \mathbb{N}$. Suppose that I have a function $f:\mathbb{N}\rightarrow\mathbb{Q}$, with initial bounds $$2 - \frac{2}{x_0} < f(x_0) = \frac{2{x_0}}{x_0 + 1} \leq 2 - \frac{5}{3x_0}.$$ ...
1
vote
1answer
30 views

A simple inequality in number theory

If $0 < a,b,c <1$, then is the following inequality true?$$a^2(b+c)+b^2(c+a)+c^2(a+b)+ab+bc+ca-a-b-c \ge0$$
2
votes
2answers
45 views

An unexplained condition on $a$ in a proof on the primes?

Lemma A positive integer $n$ is a prime if $(n,p) = 1$ for every prime integer $p \leq \sqrt{n}$ Proof in my text Let $(n,p) = 1$ for every prime $p \leq \sqrt{n} \:$. Suppose $n$ is not a ...
2
votes
0answers
46 views

$(a+b-c)(b+c-a)(c+a-b)$ divides $abc$

Do there exist pairwise distinct positive integers $a,b,c,d$ such that no two sum to another, and $(a+b-c)(b+c-a)(c+a-b)$ divides $abc$ $(a+b-d)(b+d-a)(d+a-b)$ divides $abd$? If we only require ...
-1
votes
1answer
15 views

number of days it takes to visit all the locations in matrix

The seats in a classroom are arranged into an n by m matrix. The rows are numbered from 0 to n-1 (front to back) and the columns from 0 to m-1 (left to right). After every day ,we are allowed to move ...
2
votes
4answers
70 views

Algebraic expression of Prime of form $4k-1$

Every prime of the form $4k+1$ can be written as an algebraic expresion of sum of two squares. Question: If $p=4k-1 $, can it be written as a sum of some powers? (algebraic exprssion like $p= y^3+ (...
-2
votes
2answers
46 views

Can we find three odd numbers satisfying this relation? [closed]

If $a^2+b^2=c^2$ and $(a, b, c) \in \mathbb N^3$ are natural numbers. Can we find three odd numbers satisfying this relation?
0
votes
0answers
22 views

Collatz conjecture varient prove

Every body knows that Collatz conjecture cannot be proved.It works like this: 1.For any odd number $n$ it gives $3n+1$. 2.For any even number $n$ It gives $\frac{n}{2}$. Now the problem is open ...
3
votes
3answers
85 views

For which integers $a,b,c,d$ does $\frac{a}{b}+\frac{c}{d} = \frac{a+c}{b+d}$?

For which $a,b,c,d \in \mathbb{Z}$ does $\frac{a}{b}+\frac{c}{d} = \frac{a+c}{b+d}$? This is actually the question I meant to ask in a previous question that I asked here. What about $a,b,c,d \...
0
votes
1answer
65 views

Need help with proof about Diophantine equations

The way I am planning to arrange this is by providing fragments of the proof, so I can understand what's going on before forging ahead, so if you are going to help me, keep in mind that I am going to ...
3
votes
1answer
112 views

For which integers $a,b,c,d$ does $\frac{a}{b} + \frac{c}{d} = \frac{a+b}{c+d}$?

A long time ago one of my professors gave me this question. He didn't know the answer and has since passed away. For which $a,b,c,d \in \mathbb{Z}$ does $\frac{a}{b} + \frac{c}{d} = \frac{a+b}{c+d}...
2
votes
3answers
47 views

If $a,b,c>0$, then can we find values such that the given condition is valid?

For what integer values of $a, b, c$ the expression $(1-a)(1-b)(1-c) = abc$ ?
1
vote
1answer
98 views

Generalization of the fact that $\sum_{i=1}^{n}\frac 1 i$ is not an integer for all $n>1$.

Its a generalization I thought for the following problem :- Prove that $\sum_{i=1}^{n}\frac 1 i$ is not an integer for all $n>1$. Conjecture-For any non-constant arithmetic progression $a,a+d,a+2d,...
7
votes
3answers
54 views

Prove that $\sum^{n-1}_{i=1}i^{(n-1)} \equiv -1$ (mod $n$) for all prime $n\in\mathbb{N}$.

Prove that $\sum^{n-1}_{i=1}i^{(n-1)} \equiv -1$ (mod $n$) for all prime $n\in\mathbb{N}$. I'm having a difficult time proving this problem. I was able to verify that it works for prime $n$ up to ...
1
vote
3answers
45 views

Progressions modulo $n$

I don't understand how to do these 2 tasks: 1) Prove that any arithmetic progression modulo $n$ has a period that divides $n$. 2) Prove that any geometric progression modulo a prime number $p$ has a ...
2
votes
4answers
43 views

Proving that these terms have no common factors

If $m = a_1x + b_1y$ , $n = a_2x + b_2y$ , $a_1b_2 - a_2b_1 = 1$ then prove that $\gcd (m,n) = \gcd (x, y)$ My attempt Let $c = \gcd (x,y)$ and $d = \gcd (m,n)$ then $c \mid d$ $\frac{d}{c} = \...
4
votes
2answers
84 views

The $25$th digit of $100!$

I want to find The $25$th digit of $100!$. My attempt:It is easy to know it has $24$ zeroes.Because: $\lfloor {\frac{100}{5}} \rfloor+\lfloor {\frac{100}{25}} \rfloor =24$ By getting the fist ...
17
votes
4answers
2k views

Have I found all the numbers less than 50,000 with exactly 11 divisors?

The math problem I am trying to solve is to find all positive integers that meet these two conditions: have exactly 11 divisors are less than 50,000 My starting point is a number with exactly 11 ...
2
votes
0answers
140 views

Are all theorems usable? [closed]

The (revised) question to answer: Can anyone give an example of a serious proof using this funny (revised) theorem? For any natural number $n$ and prime $p<n-1$ there exist a prime $q$ ...
1
vote
3answers
79 views

There exists infinitely many $n\in\mathbb{Z}$ such that $f(n)$ is a prime.

I found in a number theory book the following lines Let $f(x)$ be a non-constant polynomial with integer coefficients such that none of the following hold for it 1) There is an integer $d>1$ ...
1
vote
1answer
32 views

The greatest common divisor of $(O_n, T_n+2)$ where $O_n$ and $T_n$ are the oblong and triangular numbers respectively.

Suppose that $T_n$ is odd. Can we find infinitely many $n$ such that $(O_n, T_n+2)=1$? Is it trivial and obvious? My hunch based on some hand calculations is to look at $n$ congruent to $0$ or $2$ ...
3
votes
3answers
63 views

Prove that there are exactly $k$ pairs $(x,y)$ of rational numbers with $0\leq x,y<1$ for which both $ax+by,cx+dy$ are integers.

Let $a,b,c,d$ are integers such that $(a,b)=(c,d)=1$ and $ad-bc=k>0$. Prove that there are exactly $k$ pairs $(x,y)$ of rational numbers with $0\leq x,y<1$ for which both $ax+by,cx+dy$ are ...
0
votes
1answer
20 views

Arithmetic mean of the integers in set $S=\{k:k\in \mathbb{Z}, 1\leq k\leq n$ and $gcd(k,n)=1\}$

Or stated simply, what is the arithmetic mean of the totatives of $n$? From this question here I can see that the sum of the totatives is given by the formula $\large\frac{n\times\phi (n)}{2}\large$. ...
0
votes
2answers
125 views

How does $x^4+y^4=z^2 \implies x^4+y^4=z^4$?

Why is the statement "the following cannot be satisfied" for $x^4+y^4=z^2$ more strong than for $x^4+y^4=z^4?$ More specifically, how does $x^4+y^4=z^2 \implies x^4+y^4=z^4?$ This statement was ...
6
votes
0answers
91 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^...
2
votes
1answer
39 views

Statement regarding primes $ \le n$

Following is the statement I believe is true, but can't prove. Let $n$ be a natural. Let the primes less than equal to $\sqrt{n}$ be $p_1,p_2,...,p_k$. Let $\alpha_i$ be the greatest natural ...
3
votes
0answers
62 views

Algebraic number that exponentiated with algebraic number give $\pi$

I'm not sure if an algebraic number elevated with an algebraic exponent can give rise to a transcendental number. If that's the case does anybody know a closed form for an algebraic number that ...
2
votes
5answers
88 views

Find all natural numbers $n$ such that $n^{17}-n$ is divisible by 10

I've encountered this math problem and I don't know how to solve it. What math region,field(however you call it. English is not my first language) is used here ? Find all natural numbers for which ...
0
votes
1answer
35 views

No prime between these two numbers

For a fixed $k\in \Bbb N$, why is there no prime number between $(k+2)!+2$ and $(k+2)!+2+k$? My professor said this but didn't prove it.
1
vote
0answers
49 views

Intersection of two sets of rationals

I'm looking to see if anyone has any solutions or references for this problem. I'm not even sure of a proper category. It seems like it should be trivial, perhaps I'm missing something obvious. ...
3
votes
0answers
58 views

A function can provide the complete set of Euler primes via a Mill's-like constant. Is it useful or just a curiosity?

The following $f(m,n)$ function provides the complete set of Euler primes (OEIS A196230): $$f(m,n)=m^2-m+[\lfloor E^{2^n} \rfloor - {\lfloor E^{2^{n-1}} \rfloor}^2 +\frac{\lvert n-(\frac{1}{2}) \...
1
vote
2answers
42 views

Relation between HCF, LCM and product of multiple numbers [duplicate]

It is well known that for two numbers $a $ and $b$, $$\text {lcm} (a,b)\times \text {hcf} (a,b)=ab$$ Does there exist a similar equality/ inequality between HCF, LCM and product of multiple numbers? (...
9
votes
1answer
106 views

Prove that $\dfrac{b^{n-1}a(a+b)(a+2b)\cdots(a+(n-1)b)}{n!}$ is an integer

Let $a$ and $b$ be integers and $n$ a positive integer. Prove that $$\dfrac{b^{n-1}a(a+b)(a+2b)\cdots(a+(n-1)b)}{n!}$$ is an integer. Define $v_p(x)$ such that if $v_p(x) = n$, then $p^n \mid x$ but ...
1
vote
1answer
48 views

Help on an application of Dirichlet's theorem for primes in progression

Suppose that I have an infinite sequence of positive integers $$a_1,\ldots,a_m,\ldots$$ with the following recursion $$a_{m+1} -a_m =b(m+1)$$ So that $$a_{m+1} =b(m+1) +a_m$$ Suppose ...
0
votes
0answers
15 views

Steep Diagonals and Magic Squares

We want to describe via a picture a set of subsets of a square which are something like diagonals, but are not quite the same. We’ll call them steep diagonals. One of them, labelled e, is illustrated ...
2
votes
2answers
31 views

Positive integer solution $pm = qn+1$

Let $m,n$ be relatively prime positive integers. Prove that there exist positive integers $p,q$ such that $pm = qn+1$. We know Bézout's identity that there exist integers $p,q$ such that $pm+qn = 1$,...
-1
votes
0answers
20 views

Solving a system of congruences with unkown moduli?

So I have two congruences of the form: n[1]=r[1] mod m and n[2]=r[2] mod (a*m+b) with known n,r,a, and b. Is there a way way to efficiently get (an acceptable) m? Edit: I mean is there any way ...
2
votes
2answers
45 views

How many integer solutions for $a = n(4m-1)/4b$?

For the equation \begin{equation} a = \frac{n(4m-1)}{4b} \end{equation} where $n,m,a$ and $b$ are positive integers and $1\leq a,b\leq n$, how many valid, unique solutions $(a,m)$ exist for fixed $n$ ...
1
vote
2answers
117 views

Primes in the binomial transform of $ [1, 1, 2, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, …]$.

This question is related to this sequence A139482. A commentator gives the following formula for $a_m$ $$a_m = {3m^2-9m+10 \above 1.5pt 2}$$ I have that you should consider the sequence $b_n =3n+2$ ...
14
votes
7answers
921 views

Find all even numbers that can be represented as a difference of squares in only two ways

I am currently working on this proof. I am looking to find (with proof) all even numbers that can be represented as a difference of squares in only two ways. My thoughts thus far. I examined the ...
1
vote
1answer
33 views

Chartrand Mathematical Proofs 3e Exercise 5.22

I am self-studying this book, and have got stuck on this question: 5.22 Let $S=\left\{ p+q\sqrt{2}:p,q\in\mathbb{Q}\right\}$ , $T=\left\{ r+s\sqrt{3}:r,s\in\mathbb{Q}\right\}$ . Prove that $S\cap ...
5
votes
2answers
51 views

Density of primes among the prime powers

What is the relative density of the prime numbers among the set of prime powers? In particular, let $\Pi(x)$ be the number of prime powers less than $x$ and let $\pi(x)$ be the number of primes less ...