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

learn more… | top users | synonyms (1)

0
votes
0answers
9 views

rewriting one expression as other expression

Can anyone explain as how we can rewrite the first expression as second ? I am not able to pick the step done to change from 1 to 2. ...
1
vote
1answer
17 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 ...
2
votes
2answers
23 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
3answers
34 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 $4x \equiv 5 \pmod{11}$ Thus $x \equiv 4 \pmod{11} \implies x = 4 + 11k$. So, $253y = 2760 - ...
3
votes
1answer
55 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 ...
0
votes
1answer
25 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+...
2
votes
0answers
24 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'...
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
0answers
12 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, ...
3
votes
3answers
95 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
2answers
44 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
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$. ...
4
votes
1answer
30 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 (...
1
vote
2answers
36 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)...
0
votes
1answer
63 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 ...
1
vote
3answers
47 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 ...
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
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)$, ...
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) \...
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 ...
6
votes
1answer
85 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
0answers
33 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
2answers
53 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+...
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 ...
2
votes
5answers
239 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 ...
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 ...
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 ...
7
votes
1answer
78 views

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^{...
4
votes
1answer
94 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_{...
1
vote
2answers
51 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\...
1
vote
1answer
25 views

Surjectivity in proof of Chinese Remainder Thm

So we want to show that $\varphi:\Bbb Z\to \Bbb Z_m\times \Bbb Z_n, x\mapsto \left([x],[x]\right)$ descends to an isomorphism on $\Bbb Z_{nm}$ if $n, m$ are relatively prime. It's clear that $\ker \...
6
votes
1answer
90 views

If $x+y=10^{200}$ then prove that 50 divides $x$

Let $x$ be a positive integer and $y$ is another integer obtained after rearranging the digits of $x$. If $x+y=10^{200}$ then prove that $x$ is divisible by 50. My attempt Since $y$ is the digit ...
1
vote
2answers
49 views

The last eight digits of the binary development of $27^{1986}$

Find the last eight digits of the binary development of $27^{1986}$. We define $v_p(x)$ such that if $v_p(x) = n$, then $p^n \mid x$ but $p^{n+1} \nmid x$. Now we see that if $n \geq 2$ is an ...
1
vote
2answers
29 views

Chartrand Mathematical Proofs 3e Exercise 5.46

I am self-studying this book, and am stuck on this question: Prove that there exist four distinct positive integers such that each integer divides the sum of the remaining integers This is what I ...
6
votes
1answer
187 views

$m^2+2017=n^3$ has no solutions

Show that $m^2+2017=n^3$ has no solutions for positive integers $m,n$. I'm having trouble tackling this one, especially since $\mathbb{Z}[\sqrt{-2017}]$ isn't a UFD. We can write the equation as $m^...
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\...
1
vote
1answer
68 views

Parity of $\sum_{i=1}^{n}\lfloor \log_2(i) \rfloor$

Let, $L=\sum_{i=1}^{n}\lfloor \log_2(i) \rfloor $. Problem: Find $n$ for which $L$ is odd. In other words, find a closed form expression (function) $f(n)$of variable $n$ such that $L$ is odd/even if ...
0
votes
1answer
23 views

Number of subgroups of groups with prime power order

Let $G$ be a group of order $p^2$ and put $\mathcal A=\{U\leq G, \#U=p\}$. What is $\#\mathcal A$? If $G$ is cyclic, then $G$ is generated by some element $x$ of order $p^2$. It seems like there ...
3
votes
2answers
82 views

Prove that $2^{13}-1$ is prime

All prime divisors $p$ of $2^{13}-1=8191$ have $p\equiv 1\mod 26$. If $p$ divides $2^{13}-1$ then $2^{13}\equiv 1\mod p$, hence $2\in \Bbb F_p^\times$ has multiplicative order $13$. This gives us an ...
1
vote
0answers
15 views

$i \equiv k \mod p \implies i = k$ if $p$ is prime?

In a particular proof of Fermat's Little Theorem $\big(a^{p} \equiv a \mod p \big)$ in Engel, the following fact is used $i \equiv k \mod p \implies i = k \:$ where $p$ is a prime. I'm not really sure ...
3
votes
3answers
84 views

Proof about Pythagorean triples

Show that if $(x,y,z)$ is a Pythagorean triple, then $10\mid xyz$ Proof First, if $x$, $y$, $z$ are all odd, then so are $x^2$, $y^2$, $z^2$, so $x^2+y^2$ is even, which means that $x^2+y^2 \neq z^2 ...
1
vote
1answer
28 views

Find the gcd of the following Gaussian integers

$\gcd(5 + 8i, 3 + 2i)$ in $Z[i]$. I found it and I got 1 then I look at the manual solution and it turns out it can be i or -i or -1 or 1. why?
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
1answer
37 views

Proof about Gaussian integers

Show that if $\lambda \in Z[i]$ and $Norm(\lambda)=p$ where p is a prime number then $\lambda$ is prime in $Z[i]$ Approach: not so much to say $\lambda=a+bi$ where a and b are integers, so $N\lambda=...
1
vote
0answers
26 views

Confusion about the proof of If $n = 2^k - 1$ for $k \in \mathbb{N}$, then every entry in row $n$ of pascal's triangle is odd.

I saw there were existing posts for this problem (If $n = 2^k - 1$ for $k \in \mathbb{N}$, then every entry in row $n$ of pascal's triangle is odd.), but I'm still confused. This problem is in the ...
1
vote
9answers
151 views

Last digit on $3^{100}$ [duplicate]

How to find the last digit on $3^{100}$? Is there any proper method to solve such questions without calculator of course?
8
votes
0answers
94 views

How many ways can I arrange the numbers $1$ to $N$ with this divisibility condition?

For the numbers $1, \ldots, N$, how many ways can I arrange them such that either: The number at $i$ is evenly divisible by $i$, or $i$ is evenly divisible by the number at $i$. Example: for N = 2$...
2
votes
1answer
31 views

If $N = q^k n^2$ is an odd perfect number with Euler prime $q$, and $k=1$, does it follow that $\frac{\sigma(n^2)}{n^2} \geq 2 - \frac{5}{3q}$?

Let $\sigma=\sigma_{1}$ be the classical sum-of-divisors function. If $N = q^k n^2$ is an odd perfect number with Euler prime $q$ (i.e., $q$ satisfies $q \equiv k \equiv 1 \pmod 4$), and $k=1$, does ...