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

learn more… | top users | synonyms (1)

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
84 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
44 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
42 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
139 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
31 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
61 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
41 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
918 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 ...
1
vote
5answers
52 views

If $n$ is odd and $3\not\mid n \Rightarrow \ 3\mid n+1 \text{ or } 3\mid n-1 $

I'm proving that: If $3\not\mid n$ and $n$ is odd $\Rightarrow 6\mid n^2 - 1$ First, I do this: $$n^2 - 1 = (n-1)(n+1) $$ If the original proposition is true, then by unique factorization in $\...
1
vote
1answer
23 views

Let $a,b$ be positive integers that are coprime, then $ac+1=bd$ for some positive integers $c,d$.

Prove that: Let $a,b$ be positive integers that are coprime, then $ac+1=bd$ for some positive integers $c,d$. I know that by Bezout's identity, there exists integers $c',d'$ such that $ac'+bd'=1$...
5
votes
3answers
157 views

Find all integer roots of: $x^2(y-1)+y^2(x-1)=1$

Find all integer roots of: $x^2(y-1)+y^2(x-1)=1$ Obviously $(2,1)$ and $(1,2)$ are two answers. But I was unable to manipulate the equation algebraically giving a useful form for finding all other ...
4
votes
0answers
39 views

Proving there is a unique binary operation we call multiplication

The following is a theorem from the book The Real Numbers and Real Analysis by Bloch which I am currently self-studying. I am pretty sure my proof for uniqueness is correct, but I am wondering is ...
1
vote
1answer
49 views

What's the definition of a prime Gaussian integer? [closed]

The units are considered to be primes, namely, $1,-1,i,-i$. Why?
1
vote
1answer
47 views

Conjecture about divisibility: if $d \mid n$, then there exists $r,s$ such that $n=r+s$ and $d = \gcd(r,s)$

Given $n\in\mathbb Z^+$. If $d<n>1$ and $d\mid n$ it exists $r,s\in \mathbb Z^+$ such that $n=r+s$ and $d=\gcd(r,s)$.
0
votes
1answer
24 views

Need help with the proof of a theorem about Gaussian integers

Theorem 6-3. If $\alpha$ and $\beta$ are integers of $Z[i]$, and $\beta \neq 0$ then there are $\kappa$ and $\rho$ in $Z[i]$ such that $$\alpha =\beta\kappa+\rho, \text{ } N_\rho < N_\beta$$ ...
0
votes
4answers
50 views

How can be proven that any number X is greater,lesser or equal to any other number Y?

I have looked for it on the internet, really, but all I have found are particular cases like 1 > 0, or such. Is there an algebraic proof for proving that x > y or, x = y, or x < y? I thought of ...
2
votes
0answers
44 views

If $L > 1$ is an odd almost perfect number with $\omega(L)=6$, then $L$ must be divisible by $3$.

Edited July 15 2016 Let $\mathbb{N}$ denote the set of positive integers. Let $\sigma = \sigma_{1}$ denote the (classical) sum-of-divisors function. Let $I(x) = \dfrac{\sigma(x)}{x}$ denote the ...
4
votes
2answers
34 views

Smallest chain of consecutive integers not all coprime

Let $t$ be a positive integer. What is the smallest $t$ for which we can find an integer $a$ such that each element of the set $\{a+1,a+2,\dots ,a+t\}$ is not coprime with all other elements of the ...
2
votes
0answers
51 views

lower bound for sum of distinct n-th roots of unity

Given a positive integer $n$, define $\zeta = e^{2\pi i/n}$ and define $s: \mathbb Z^n \to \mathbb C$$$s(\vec x) = \sum_{k=0}^{n-1} x_k \zeta^k$$ Let us consider the set $S = \{ |s(\vec x)| : \vec x \...
1
vote
2answers
39 views

Can it proved that the GCD does not divide the integer coefficients in the linear form of the GCD?

Let $d = (a,b)$ then $d = ax +by$ for some $x,y \in \mathbb{Z}$ I want to prove that $d \nmid x,y$. Motivation I'm trying to solve the following problem: If $a$ is prime to $b$ and $y$, $b$ is ...
2
votes
8answers
196 views

Showing that $2^6$ divides $3^{2264}-3^{104}$

Show that $3^{2264}-3^{104}$ is divisible by $2^6$. My attempt: Let $n=2263$. Since $a^{\phi(n)}\equiv 1 \pmod n$ and $$\phi(n)=(31-1)(73-1)=2264 -104$$ we conclude that $3^{2264}-3^{104}$ is ...
3
votes
1answer
168 views

Generalization of Inkeri's primality test

How to prove that following hypothesis is true ? Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are ...
0
votes
2answers
22 views

Prove that the modular congruence holds: $b^d$ $=$ $r \pmod n$, $b^{d/q}$ $=$ $x \pmod n$, then $x^q$ $=$ $r \pmod n$.

Prove that if $b^d$ $=$ $r \pmod n$ $b^{d/q}$ $=$ $x \pmod n$, then $x^q$ $=$ $r \pmod n$ for any integers $b$, $n$, $r$, and $q$ (which divides $d$). Or more simply that $b^d$ $=$ $x^q$ $\...