This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

learn more… | top users | synonyms (1)

0
votes
1answer
46 views

Is there a way to prove that 2y(y-1) is divisible by four other than by means of induction?

I am going trough some of my older textbooks and in one problem you have to prove that 2y(y-1) is divisible by four if y is a whole number. Its trivial to prove this by using induction, but this ...
3
votes
0answers
49 views

Why is this not a poset after adding zero?

The problem    Consider the following set for divisibility. {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 96}. If 0 is added, the divisibility relation set will no longer be a poset. Please ...
2
votes
1answer
46 views

What does a distributed lattice have to do with GCD and LCM?

$\newcommand{\lcm}{\operatorname{lcm}}$I am lost while following this explanation: Let $$A(g, i) = \gcd(F_{g}, \lcm(F_{a_1}, F_{a_2}, \ldots , F_{a_i}))$$ and $$X = \lcm(F_{a_1}, F_{a_2}, \ldots , ...
1
vote
0answers
51 views

Calculating number which is divisible by a given number, knowing only pieces of the number

I'm given a number 'C' in a known base, and the first few digits 'D' (rightmost) of the other number, in the same base. I'm also told that a certain number of a digit 'E' can be appended to the end of ...
0
votes
1answer
35 views

Testing the divisibility of $\sum_{k=0}^{m-1} (n+k) $ by $m$ when $m$ is odd

The theorem I am attempting to test is $$ \forall m, n \in \mathbb{Z}, n > 0, m \space odd \space \Rightarrow m | \sum \limits _{k=0}^{m-1} (n+k) $$ Please note: The object of this code is to ...
1
vote
1answer
21 views

Find $v_p\left(\binom{ap}{bp}-\binom{a}{b}\right)$, where $p>a>b>1$ and $p$ odd prime.

Find $v_p\left(\binom{ap}{bp}-\binom{a}{b}\right)$, where $p>a>b>1$ and $p$ odd prime. Here $v_p(k)$ denotes the largest $\alpha\in\mathbb Z_{\ge 0}$ s.t. $p^\alpha\mid k$. We have ...
3
votes
2answers
55 views

Prove $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$.

Prove $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ for $0\ne a,b,c\in \Bbb{Z}$. I tried solving it with sets but I sense there are some details I am missing. I would truly appreciate your reference.
3
votes
3answers
90 views

Let $a,b$ be positive integers such that $a\mid b^2 , b^2\mid a^3 , a^3\mid b^4 \ldots$ so on , then $a=b$?

Let $a,b$ be positive integers such that $a\mid b^2 , b^2\mid a^3 , a^3\mid b^4 \ldots$ that is $a^{2n-1}\mid b^{2n} ; b^{2n}\mid a^{2n+1} , \forall n \in \mathbb Z^+$ , then is it true that $a=b$ ?
11
votes
7answers
998 views

Proof that $2^{222}-1$ is divisible by 3

How can I prove that $2^{222}-1$ is divisible by three? I already have decomposed the following one: $(2^{111}-1)(2^{111}+1)$ and I understand I should just prove that $(2^{111}-1)$ is divisible by ...
6
votes
3answers
87 views

If $\gcd(a,b)=1$ then $\gcd(a^2+b^2,a+2ab)=1$ or $5$

The question is already in the title. Show that if $\gcd(a,b)=1$ then $\gcd(a^2+b^2,a+2ab)=1$ or $5$. I saw yesterday this exercise in a book and I tried many things but I managed to show ...
0
votes
6answers
157 views

Proof: $\;n^2\;$ is even if and only if $\;n\;$ is even.

Please help how would you go about doing this? I'm studying for a final. This is on a study guide. I'm having a lot of trouble with this class. Prove that $n^2$ is even if and only if $n$ is even. ...
3
votes
2answers
1k views

Smallest possible integer for when $\dfrac{x}{10}$ leaves a remainder of 9 and so on

I'm in 8th grade and my geometry teacher recommended that I read the art of problem solving. So I did and I have now read the chapter called "Integers". I am now doing some of the problems in the ...
3
votes
6answers
65 views

Common divisor of $a+b$ and $ab$. [duplicate]

If $\gcd(a,b) =1$. Why does $\gcd(a+b,ab)=1$ ? I know that if $\gcd(a,b)=1$ then there exists $u$ and $v$ where $au+bv=1$. But I can't seem to relate it to $a+b$ and $ab$.
2
votes
0answers
286 views

Prime numbers with binomial coefficients

Let $p$ be an odd prime and $n$ a positive integer. Prove that $p+1$ divides $n$ if and only if $$\sum_{k\equiv j\pmod{p-1}}^n\binom{n}{k}(-1)^{\frac{(k-j)}{p-1}}\equiv 0 \mod p$$ for every $$j\in ...
2
votes
2answers
71 views

Proving if it is prime

I'm quite lost on how to prove things, with the $n \choose k$ and proving. So the question is: Prove that $n \choose k$ is divisible by $n$ if $n$ is a prime number and $1 \le k\le n-1$ Like, how ...
0
votes
1answer
53 views

What is the point of the common divisibility trick for $7$?

The "divisibility rule" to test whether a given integer is divisible by $7$ (or, more generally, to find the remainder when an integer is divided by $7$) is in my opinion, ridiculous. The method is so ...
11
votes
1answer
155 views

$ 0 < a < b\,\Rightarrow\, b\bmod p\, <\, a\bmod p\ $ for some prime $p$

If $\,a < b\,$ are natural numbers then a prime $\,p\,$ exists such that $\ a\bmod p\, >\, b\bmod p.$ The task seems understandable, but I have no idea how to prove this statement.
1
vote
1answer
23 views

if $p \mid (a^2 + b^2 )$, $p \nmid a$ and $p \nmid b$. Prove that there exists an integer $c$ such that $c^2 \equiv −1 \mod p$.

Given $p$ is prime, I'm not really sure what im supposed to do with the information that $p \nmid a$ and $p \nmid b$ in order to conclude $c^2 \equiv −1 \mod p$.
-1
votes
1answer
52 views

The greatest integer which divides the number $101^{100} - 1$ is? [closed]

Can anyone please help me on how to solve this problem? It's little urgent. Thank You
6
votes
3answers
116 views

Prove that, $(2\cdot 4 \cdot 6 \cdot … \cdot 4000)-(1\cdot 3 \cdot 5 \cdot …\cdot 3999)$ is a multiple of $2001$

Prove that the difference between the product of the first 2000 even numbers and the first $2000$ odd numbers is a multiple of $2001$. Please show the method. I have started with the following ...
1
vote
3answers
53 views

Proof involving gcd and congruence.

So here is the statement: $m \in \mathbb{N} $ and $ a,b \in \mathbb{Z}$. Prove that $gcd (a,m)=gcd(b,m)$ iff there are solutions to the linear congruences $ax\equiv b\,(\text{mod}\,\, m)$ and ...
0
votes
0answers
15 views

Under what conditions is a tower of quadratic extensions a UFD, GCD domain, or just an Integral Domain?

I have been studying towers of quadratic extensions to $\mathbb Q$ and have noticed the following: $\mathbb Q[\sqrt 2]$ and $\mathbb Q[\sqrt 2][\sqrt 3]$ are unique factorization domains(UFDs), but ...
1
vote
1answer
43 views

Proof with congruence and primes. $(p\mid a^2+b^2)(p\not\mid a,p\not\mid b)\implies \exists c\in\mathbb Z( c^2=-1\pmod {p})$.

The statement is as follows: $ p|(a^2+b^2), p\not\mid a, p\not\mid b$ . Prove there exists an integer $c$ such that $c^2\equiv -1 \pmod p$. What I tried to do is apply definition of congruence to ...
2
votes
1answer
18 views

Prove the following conditional divisibility

If $gcd(a,b)=1$ and $n$ is a prime number,then prove that $\frac{(a^n + b^n)}{(a+b)}$ and $(a+b)$ have no factors in common unless $(a+b)$ is a multiple of $n$. I don't know how to establish the ...
1
vote
1answer
78 views

Use the second isomorphism theorem to conclude that $\gcd(a,b)\text{lcm}(a,b)=ab$

Use the second isomorphism theorem to conclude that $\gcd(a,b)\operatorname{lcm}(a,b)=ab$; that is, the product of the greatest common divisor and the lowest common multiple of $a,b$ is equal to ...
5
votes
1answer
97 views

$2n\choose n$ is divisible by all the primes between $10$ and $30$.

Find the smallest positive integer $n$ such that $2n \choose n$ is divisible by all the primes between $10$ and $30$.
3
votes
1answer
59 views

Prove $\forall n\geq 2,n\in\mathbb{Z}$, $(n+1)\mid(n^3+1)$

Question: Prove $\forall n\geq 2,n\in\mathbb{Z}$, $(n+1)\mid(n^3+1)$ I know that it is possible to solve by factoring $n^3+1$ and showing that $n+1$ is a multiple, but I would like to show this via ...
1
vote
4answers
114 views

If $ \sqrt{n}^k$is an integer, then $n \mid\sqrt{n}^k $ [closed]

Suppose $n$ is an odd integer and $k \in \mathbb{N}$ with $k \geq 2$. How can I show the following statement? $$ \sqrt{n}^k \ \text{is an integer}\ \Longrightarrow n \mid\sqrt{n}^k $$
1
vote
5answers
106 views
0
votes
1answer
40 views

A question regarding the greatest common divisor

Good day to everyone! I just have a quick question regarding the greatest common divisor function. Say I have $\gcd(m,n^2)=1$. Does it follow that $\gcd(m,n)=1$? Here is my attempt at a proof: ...
1
vote
1answer
48 views

Why is $\frac{\gcd(c_2,c_3)}{\gcd(c_1,c_2,c_3)}=\gcd\left(\frac{c_2}{\gcd(c_1,c_2)},c_3\right)$

Why is true that $\operatorname{lcm}(\gcd(c_1,c_3),\gcd(c_2,c_3))=\gcd(\operatorname{lcm}(c_1,c_2),c_3)$ ? LHS is $\displaystyle\frac{\gcd(c_1,c_3)\gcd(c_2,c_3)}{\gcd(c_1,c_2,c_3)}$ RHS is ...
2
votes
5answers
81 views

I am looking to show that $n$, $n + 1$, or $n + 2$ are divisible by 3

I am seeking to prove the following: If $n \in \mathbb{Z}$, then exactly one of the following is true: $\frac{n}{3} \in \mathbb{Z}, \frac{n + 1}{3} \in \mathbb{Z}, \frac{n + 2}{3} \in \mathbb{Z}$. I ...
1
vote
1answer
25 views

$(a,bc)=\frac{(a,b)(a,c)}{(a,b,c)}$ : when is this gcd-identity true?

Let $a$, $b$ and $c$ be integers and let $(.,.)$ denotes the $\operatorname{gcd}$ function. When is this indentity true : $$(a,bc)=\frac{(a,b)(a,c)}{(a,b,c)} \quad ?$$ Many thanks !
3
votes
1answer
44 views

If ${a}$ is an arbitrary integer, then prove that ${360|a^2(a^2-1)(a^2-4)}$.

I think I have solved the problem. I want to verify my proof, since I don't have a teacher to help me. Proof: Since, ${360=8*45}$ and ${gcd(45,8)=1}$, hence if we can prove that ...
4
votes
6answers
74 views

Prove by mathematical induction that $\forall n \in \mathbb{N}: 20~|~4^{2n} + 4$

Prove by mathematical induction that $\forall n \in \mathbb{N}: 20~|~4^{2n} + 4$ Step 1: Show that the statement is true for n = 1: $4^{2 \cdot 1} + 4 = 20$ Since $20~|~20$, the base case is ...
1
vote
4answers
102 views

How to prove it is always divisible by 6 [closed]

Prove that $n(n^2 − 7)$ for is always divisible by 6. (for any natural number $n$) I have no idea.
5
votes
6answers
124 views

Proving that $7^n(3n+1)-1$ is divisible by 9

I'm trying to prove the above result for all $n\geq1$ but after substituting in the inductive hypothesis, I end up with a result that is not quite obviously divisible by 9. Usually with these ...
0
votes
1answer
24 views

What is the condition for the third variable (divisibility)?

If: $$5 | x + y + z$$ Meaning, 5 divides $x+y+z$ Where $x,y, z$ are integers. They said, if $x, y$ are ARBITRARY there are only two possibilities for $z$? How to do this type of problem?
0
votes
0answers
33 views

Less-ugly proof of infinitude of primes of form 6N+1

While reviewing a free online algebra text I came across this problem in the sort of remedial section of the book: Prove that there are an infinite number of primes of the form $6n + 1$. I had a ...
0
votes
2answers
71 views

Prove: p-mq | f(m) where 'm' is any integer

How to prove that $p-mq \mid f(m)$ where $m$ is any integer, $f(x) = A_0 + A_1 x + A_2 x^2 + ... + A_{n-1} x^{n-1} + A_n x^n$, $f(x)∈ ℤ[x]$, $p/q$ is a zero for $f(x)$ and $p$ and $q$ are coprime ...
0
votes
2answers
77 views

How to find the remainder $x^y\bmod z$ quickly?

I am searching for any rule to find the remainder $x^y\bmod z$ where $x,y,z$ are positive integer. Is there any rule to quickly find this remainder (without computing $x^y$)?
6
votes
4answers
146 views

Efficiently producing certain kinds of examples of the application of Euclid's algorithm

Is there some efficient way to churn out pairs of integers $n,m$ such that $\gcd(n,m)=1$; $n,m$ both have fairly large numbers of fairly small prime factors; and Euclid's algorithm applied to $n,m$ ...
2
votes
2answers
37 views

Simple Division Proof

Prove that for every three integers i, j, and k, if i $\nmid$ jk, then i $\nmid$ j We've just started proofs and I am at a complete loss for how to go about doing it. I've tried proving through ...
11
votes
2answers
229 views

Show that $A[X]/(aX+b)$ is an integral domain

Let $A$ be an integral domain, $a$ and $b \in A-\{0\}$, and let $B = A[X]/(aX+b)$. Show that, if $Aa \cap Ab=Aab$, then $B$ is an integral domain. My attempt at proof (following a hint). Denote ...
3
votes
2answers
71 views

$f,g,h$ are polynomials. Show that…

Let $f,g$ and $h$ be polynomials. Show that $\gcd(f,g,h)=\gcd(\gcd(f,g),h)$. I was thinking of signing $\gcd(f,g)=d$ and then write it by using Euclid's algorithm, but I couldn't get anything proper. ...
1
vote
3answers
61 views

Prove $4|10^n \iff n>1$

I am just wondering if it is true that $4|10^n \iff n>1$. I was thinking that it is because $2|10$ and $2\cdot2=4$ so $4|10^2$ but not $10$ so $n > 1$.
3
votes
5answers
118 views

Show that $2222^{5555} + 5555^{2222}$ is divisible by $ 7$ [duplicate]

Show that $2222^ {5555} + 5555 ^ {2222}$ is divisible by $7$. I tried factorizing but it didnt lead to anything. Can divisibility rules be used? Any ideas please tell me.
2
votes
3answers
189 views

Polynomial division challenge

Let $x,y,n \in \mathbb{Z} \geq 3$, Find $A,B$ such that $$x^{n-1}+x^{n-2}y+x^{n-3}y^2+\cdots+x^2y^{n-3}+xy^{n-2}+y^{n-1}= A(x^2+xy+y^2)+B$$ What is the best method to approach this?
2
votes
2answers
67 views

Connection between GCD and totient function

I found the following formula which connects Euler's totient function with gcd at wikipedia. $$ \gcd(a,b) = \sum_{k|a \; \hbox{and} \; k|b} \varphi(k). $$ The problem is that I can not figure out ...
3
votes
2answers
101 views

Divisors of $2^{2^{127}-1}-1$

Consider the recursively defined number sequence $f(0) = 2$ $f(n+1) = 2^{f(n)}-1$ This sequence goes like $2$, $3$, $7$, $127$, $2^{127}-1$, $2^{2^{127}-1}-1$, $\ldots$. Facts: $2$, $3$, ...