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

learn more… | top users | synonyms (1)

0
votes
3answers
43 views

Solve $391x + 253y = 2760$ integer $x, y$

Solve $391x + 253y = 2760$ integer $x, y$ I took some mods: $138x \equiv 230 \pmod{253}$ this means $3x \equiv 5 \pmod{11} \implies x \equiv 9 \pmod{11}$ Thus $ \implies x = 9 + 11k$. So, $253y =...
-1
votes
3answers
58 views

How many positive integers $a, b, c$ satisfy $a + 2b + 3c = 2016$?

I have to find the number of non-negative/positive integer solutions of $$a + 2b + 3c = 2016.$$ I got this question and can't solve it, any hint?
1
vote
1answer
388 views

Sums of consecutive odd integers, positive or negative

While supervising a student competition, my colleague and I ran across an interesting problem. Deobfuscated, it boils down to this Given a limit value $M$, which integers in the range $1,\dotsc,M-...
2
votes
2answers
82 views

How Deficient a Number is? (Finding numbers having a certain deficiency)

This question was edited, in particular equations were corrected: A number N is said to be deficient by an integer $d$ if: $\sigma(N)=2N-d$ Note that powers of 2 are deficient by 1. While a prime $...
1
vote
1answer
24 views

Small primes congruent to $a$ mod $p$.

Let $p$ be a prime and $a$ be an integer such that $0 \lt a \lt p$. Is there a prime number, $q$, congruent to $a$ mod $p$ such that $q\lt p^2$? I have checked that this is true for the first $3000$...
8
votes
2answers
104 views
+50

How to prove by induction that $3^{3n}+1$ is divisible by $3^n+1$ for $(n=1,2,…)$

So this is what I've tried: Checked the statement for $n=1$ - it's valid. Assume that $3^{3n}+1=k(3^n+1)$ where $k$ is a whole number (for some n). Proving for $n+1$: $$3^{3n+3}+1=3^33^{3n}+1=3^3(3^{...
7
votes
1answer
97 views

Theoretical way to prove no positive integer $n$ exists such that $n+3$ and $n^2+3n+3$ are both perfect cubes.

I have to prove that for any positive integer $n$ at least one of $n+3$ and $n^2+3n+3$ is not a perfect cube. Is there a methodical way to solve this problem? I managed to solve it by contradiction, ...
1
vote
3answers
50 views

Show that if $n \equiv 3 (mod 4)$, then n has a prime factor $p \equiv 3 (mod\text{ } 4)$

Show that if $n \equiv 3(mod\text{ } 4)$, then $n$ has a prime factor $p \equiv 3(mod\text{ } 4)$ Approach: By definition any prime number can be represented as a product of primes, so let $n=p_1*....
3
votes
3answers
111 views

Infinitely many primes $\equiv 3 \mod 4$

Question 1 Is the following proof of the infinitude of primes $\equiv 1\mod 4$ okay? Consider a prime divisor $p\mid (n!)^2+1$. Then $(n!)^2\equiv -1 \mod p$, hence $n!$ has multiplicative order $4$ ...
1
vote
1answer
21 views

$\left(\frac{3}{p} \right)=1$ iff $p\equiv 1\pmod{12}$ or $p\equiv -1\pmod{12}$

Let $p\geq 5$ be a prime. $\left(\frac{3}{p} \right)=1$ iff $p\equiv 1\pmod{12}$ or $p\equiv -1\pmod{12}$. So $\left(\frac{3}{p} \right)=\left(\frac{p}{3} \right)\cdot (-1)^{(p-1)/2}$ and this ...
0
votes
2answers
68 views

For all $x$ , $x^2 \equiv 0$ or $1$ or $4 \mod 7$

My textbook makes the following claim For any $x$ , $x^2 \equiv 0$ or $1$ or $4 \mod 7$ I can't see how this true though. $3^2 \equiv 4^2 \equiv 2 \mod 7$ so this obviously doesn't fall into ...
2
votes
0answers
25 views

a particular linear combination

Fix $a_1,\ldots,a_n\in\mathbb{N}$. I'd like to know if one can characterize the natural numbers that belong to the set $$\{b_1a_1+\ldots+b_na_n:\,b_j\in\{-1,0,1\}\}.$$ EDIT: Maybe this question doesn'...
2
votes
2answers
26 views

Find the Wrong Student

There are 15 student in the class and each of them has a different number 1 to 15. Student #1: wrote the natural number on the board. Student #2 said : This number is divisible by my number(number ...
1
vote
2answers
47 views

Modular arithmetic - solving logarithmic equation given logarithmic list of different base

Suppose we are working in a prime modulus $p$, and we are given a list of the discrete logarithms of a particular base $b$ which is a primitive root. What is the significance of that list of discrete ...
23
votes
3answers
2k views

Find a thousand natural numbers such that their sum equals their product

The question is to find a thousand natural numbers such that their sum equals their product. Here's my approach : I worked on this question for lesser cases : \begin{align} &2 \times 2 = 2 + 2\\ ...
0
votes
1answer
26 views

What is the greatest remainder if you divide a 2-digit number by its digit sum

I just found this problem and tried to solve it. I wrote $x=90a+b$ and tried to maximize the function $f(a,b)=\frac{9a+b}{a+b}$ but did not come to any solution. Then I considered $10a+b = x\pmod{a+...
1
vote
5answers
70 views

Proof that $n = 3k + 5l$ for $n > 7$

Show that for every n greater than $7$, there are non-negative integers $k$ and $l$ such that $$n = 3k+ 5l.$$ So induction seems like a possibility. $n = 3k + 5l$ and so $n + 1 = 3k + 5l + 1$. ...
3
votes
1answer
56 views

Proving $\sqrt{2}$ is irrational: why $ q = p - \frac{p^2 -2}{p+2}$ [duplicate]

I've just begun self-studying Rubin's Principals of Mathematical Analysis. I'm having difficulty understanding a specific line in example 1.1 (proving $\sqrt{2}$ is irrational). Specifically, I'm ...
3
votes
2answers
79 views

Finite summation including binomial coefficients and double factorials

I came across the following summation: $$ \sum_{k=0}^n\frac{(-1)^k(2k)!!}{(2k+1)!!}\dbinom{n}{k}\,\,\,\,(n\in\mathbb{N}). $$ $\tbinom{n}{k}$ are binomial coefficients, $n!/k!(n-k)!$. Mathematica told ...
0
votes
2answers
22 views

Colors on sets $S=\{1,2 \cdots ,1000\}$.

To each element of sets $S=\{1,2 \cdots ,1000\}$ a color is assigned. Suppose that for any two elements $a$ and $b$, of $S$,if $15$ divides $a+b$, then they both are assigned with same color. What is ...
1
vote
2answers
46 views

Find non-diagonal matrices $A$ and $B$ such that $B^TAB$ is diagonal

Here $B^T$ denotes the transpose of $B$. $A$ and $B$ are invertible $3\times 3$ matrices with integer entries. $A$ is symmetric positive definite with at most two zero entries. We want the ...
1
vote
0answers
14 views

Application of Structure Theorem to Prove Simultaneous Diagonalizability and Group of Units of Cyclic Groups

I am reading these notes on Modules over PID. Exercise 67 (pg 24) asks to prove that: Problem. Let $A$ and $B$ be $n\times n$ matrices with complex entries. Then $A$ and $B$ are simultaneously ...
2
votes
1answer
39 views

$\Bbb Z[\sqrt{-5}]$ is not a PID [duplicate]

I want to show: In a PID $R$ two elements $a,b\in R$ always have a greatest common divisor. Therefore $\Bbb Z[\sqrt{-5}]$ is not a PID. For the first part: $I=\{ax+by:x,y\in R\}$ is an ideal, ...
0
votes
1answer
44 views

Is the following inequality involving the sum-of-divisors and Euler totient functions true?

First Question Is the following inequality involving the sum-of-divisors $\sigma$ and Euler totient $\phi$ functions true? $$\frac{\sigma(N)}{N} \leq \frac{N}{\phi(N)}$$ Second Question When $...
0
votes
1answer
64 views

Having no derangements — any advantage?

Is there any problem-solving advantage when a sequence has no derangements? In an Erd\"os proof of Sylvester-Schur he identifies a few exceptions which I contend would not happen if his sequence had ...
4
votes
1answer
31 views

Non-negative integer solutions to $4ab-a-b=c^2$

The puzzle is as follows: Problem: Find all non-negative integer solutions to $4ab-a-b=c^2$ My Progress: There is, of course, the trivial solution of $a=b=c=0$, and I suspect there are no more (...
10
votes
4answers
3k views

Fibonacci sequence divisible by 7?

Make and prove a conjecture about when the Fibonacci sequence, $F_n$, is divisible by $7$. I've realized it's when $n$ is a multiple of $8$. I just don't know how to go about proving it.
2
votes
5answers
240 views

A statement about divisibility of relatively prime integers

I'm solving a problem, and the solution makes the following statement: "The common difference of the arithmetic sequence 106, 116, 126, ..., 996 is relatively prime to 3. Therefore, given any three ...
1
vote
2answers
37 views

Dirichlet inverse of $(-1)^n$

I was tinkering around and noticed the Dirichlet inverse of $\,f(n) = (-1)^n$ seems to be $$ f^{-1}(n) = -\mu\!\left(n\,/\,2^{\nu_2(n)}\right)\left\lceil 2^{\nu_2(n)-1} \right\rceil, $$ where $\nu_p(n)...
20
votes
4answers
3k views

Can a finite sum of square roots be an integer?

Can a sum of a finite number of square roots of integers be an integer? If yes can a sum of two square roots of integers be an integer? The square roots need to be irrational.
1
vote
3answers
48 views

Solve the equation $(x+y)^2 + 3x + y + 1=z^2$ over positive integers.

Solve the equation $(x+y)^2 + 3x + y + 1=z^2$ where $x, y, z \in \mathbb{N}$ I've found some solutions, like $(0, 0, 1), (1, 1, 3)$ and, more general, $x=k,y=k,z=2k+1$. No idea how to prove or ...
1
vote
0answers
55 views

Induction Method in a special case of $ n!+1 = m^2 $ (Brocard's Problem)

Context: Brocard's problem is a problem in mathematics that asks to find integer values of $n$ and $m$ for which$$ n!+1 = m^2 \tag{1}$$ Let's define, $$T=\left(\left\lfloor \frac{ (\lfloor\log(n) \...
6
votes
1answer
88 views

Number of integer triplets $(a,b,c)$ such that $a<b<c$ and $a+b+c=n$

What is an equivalent combinatorial presentation for the problem? Can I use the stars and bars approach to find the number of integral solutions of $a+b+c=n$ where $a,b,c\geq 0$? If in addition $a+b&...
0
votes
1answer
29 views

Probability of choosing a number from the set $\{1,2,\ldots,99\}$ that divided by $5$ has the remainder $2$ and is a multiple of $3$

Good evening to everyone. I have to find the probability of choosing a number from the set {1,2...99} that divided by 5 has the remainder 2 and at the same time it's multiple of 3. I know that the ...
0
votes
0answers
50 views

Right angled triangle and Pythagorean triplet

Show that there exists a right angled triangle with rational sides and area $d$ if and only if $x^2,y^2$ and $z^2$ are squares of rational numbers and are in arithmetic progression with common ...
2
votes
7answers
122 views

Find all positive integer roots of : $5xy=19x+96y$

Find all positive integer roots of : $5xy=19x+96y$ I tried using decomposition technique but no success...,it seems suitable factorization of this equation is IMPOSSIBLE!! Handy calculations show ...
0
votes
1answer
45 views

$n$ divides $2^n-1$ $\implies n=1$

If $n\mid (2^n-1)$, then $n=1$. Somehow I am unsure if I got this right, my 'proof' seems to 'easy'. Can you please give me feedback? So I take a prime divisor $p\mid n$. Then $p\mid (2^n-1)$, ...
5
votes
3answers
156 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 ...
1
vote
2answers
52 views

Is $2\prod_{i=1}^{n}{p_i} - \prod_{i=1}^{n}{(p_i + 1)} - \prod_{i=1}^{n}{(p_i - 1)}$ even and negative for $n > 1$?

Is $$2\prod_{i=1}^{n}{p_i} - \prod_{i=1}^{n}{\left(p_i + 1\right)} - \prod_{i=1}^{n}{\left(p_i - 1\right)}$$ even and negative for $n > 1$, where $p_i > 1 \hspace{0.07in} \forall i \in \left[1,n\...
0
votes
0answers
35 views

General strategies solving non linear congruence

I am trying to complete a nice summary for solving non-linear modular equations as i couldn't find a good one. I mean the specific (but still very wide) case of the form $f(x)\equiv0 \mod m$ where $f(...
0
votes
1answer
30 views

Real polynomials from repunits to repunits ( Putnam 2007 A4) [closed]

Find all polynomials $ f$ with real coefficients such that if $ n$ is a repunit, then so is $ f(n).$ [Note this is a Putnam question, so it is intended to be of easy to middling difficulty as contest ...
0
votes
2answers
54 views

$(1^n+2^n+3^n+4^n)\mod5$ and using euler totient function to solve this

The problem gives us an integer $n$ which can be extremely large (can exceed any integer type of your programming language) and we need to calculate the value of the given expression . $$(1^n+2^n+3^n+...
2
votes
4answers
229 views

Sums of two perfect squares

Show that if $q$ is a number that can be expressed as the sum of two perfect squares, then $2q$ and $5q$ can also be expressed as the sum of two perfect squares. EDIT: I've recently revisited this ...
7
votes
0answers
66 views
+50

Greedy algorithm Egyptian fractions for irrational numbers - patterns and irrationality proofs

This is related to another question on this site, but it's not a duplicate, because the actual questions I ask are completely different. In one of the answers Jeffrey Shallit provided a very useful ...
0
votes
2answers
27 views

Given a set of 6 numbers, can 3 of them be reversibly represented as even numbers?

Given a set of 6 arbitrary numbers between the range of 0 - 8 inclusive, i.e. 2, 5, 0, 4, 1, 7 (duplicates are allowed) Is there a way the first 3 numbers can be ...
1
vote
6answers
56 views

Prove by induction that $a^{4n+1}-a$ is divisible by 30 for any a and $n\ge1$

It is valid for n=1, and if I assume that $a^{4n+1}-a=30k$ for some n and continue from there with $a^{4n+5}-a=30k=>a^4a^{4n+1}-a$ then I try to write this in the form of $a^4(a^{4n+1}-a)-X$ so I ...
2
votes
2answers
100 views

How does this technique for solving simultaneous congruences work?

Find $x\in \Bbb Z$ with $x\equiv 3 \mod 7$ $x\equiv 9 \mod 11$ $x\equiv 1 \mod 5$ So here's what I do: I first find $r_1\in \Bbb Z$ with $r_1\equiv 1 \mod 7$ and $r_1\equiv 0 \mod(11\...
4
votes
1answer
95 views

For which values of $n$ the sum $\sum_{k=1}^n k^2$ is a perfect square?

Question. For which values of $n$ the sum $\sum_{k=1}^n k^2$ is a perfect square? Clearly, $n=24$ is one such value, and I was wondering whether this is the only value for which the above holds. The ...
1
vote
0answers
20 views

Why is $ \theta(m) \propto \zeta(2) $ if it is counting lattice points in a hyperbola?

I found this lattice point identity in a derivation of $\zeta(2)$: $$ \theta(x) = \sum_{mr \leq x} m = \sum_{r \leq x}\sum_{m=1}^{[x/r]} m = \sum_{r \leq x} \left( [x/r]^2 + [x/r] \right) = \sum_{...
4
votes
4answers
211 views

No solution for the equation $y^{n} = 2x^{n}$ for $n \geq 2$ in positive integers.

Exercise from Nathanson's book. Let $n \geq 2$. Prove that the equation $y^{n}=2x^{n}$ has no solution in positive integers. Attempt: We can write the equation as $y^{n}-x^{n} = x^{n}$. I ...