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)

3
votes
1answer
38 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
101 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
122 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
23 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
32 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
70 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
145 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
35 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
221 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
69 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
60 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$.
2
votes
5answers
100 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
185 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
56 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$, ...
2
votes
2answers
41 views

Divisibility of three polynomial terms

So here is the statement that im having trouble proving: If $9\mid x^3+y^3+z^3$ then $3\mid xyz$ for integers $x,y,z$. I tried applying the definition of divisibility but that doesn't seem to ...
0
votes
0answers
42 views

Most general GCD (commutative) ring

I'd like to know much about GCD in general commutative rings. Do you have books, sites or articles to recommend ? There is a lot to read about GCD in integral domain, but almost nothing in ...
7
votes
3answers
315 views

Invert and subtract, is there any explanation?

I see in many Brazilian sites that, if you get a number and subtract it by its reverse, you will have zero or a multiple of nine. For example: ...
-1
votes
3answers
47 views

Prove that $\forall n \in \mathbb Z,\;n^2 + 1$ is not divisible by $3$ [closed]

"Prove that $n^2+1$ is not divisible by $3$ for any integer n." How to prove this?
1
vote
1answer
56 views

Finding the inverse modulo . $7^{-2}\pmod {11}$ and $7^{-3}\pmod {11}$

$7^{-1}\pmod{11}$ the above can be found by $7x\pmod{11}\equiv 1$ and $x=8$ now i am confused on how to find $7^{-2}\pmod{11}$ and $7^{-3}\pmod{11}$ .
4
votes
2answers
58 views

Proper divisors of 1?

What are the proper divisors of 1? I understand proper divisors do not include the number itself, but is 1 an exception or does it have no proper divisors?
7
votes
4answers
99 views

Show $17$ does not divide $5n^2 + 15$ for any integer $n$

Claim: $17$ does not divide $5n^2 + 15$ for any integer $n$. Is there a way to do this aside from exhaustively considering $n \equiv 0$, $n \equiv 1 , \ldots, n \equiv 16 \pmod{17}$ and showing $5n^2 ...
1
vote
2answers
52 views

Show that for every $n > 1$ there exist $n$ consecutive composite numbers [duplicate]

So I am trying to prove that for every $n > 1$ there exist $n$ consecutive composite numbers but I do not know even how to start. This is a problem in analytic number theory. Please can you help ...
3
votes
3answers
95 views

How can I demonstrate that $x-x^9$ is divisible by 30?

How can I demonstrate that $x-x^9$ is divisible by $30$ whenever $x$ is an integer? I know that $$x-x^9=x(1-x^8)=x(1-x^4)(1+x^4)=x(1-x^2)(1+x^2)(1+x^4)$$ but I don't know how to demonstrate that ...
1
vote
5answers
51 views

Show $\nexists k:3^7\mid k!$ but $3^8\nmid k!$

Show $\nexists k:3^7\mid k!$ but $3^8\nmid k!$ Ideas: I need to find integer $m$ such that $m=\frac{k!}{3^7}$ and $m\neq\frac{k!}{3^8}$, but I have 2 unknowns so don't know how to proceed from here. ...
2
votes
2answers
22 views

proof : $a,b \in N, a^5 | b^5 \rightarrow a | b$

I couldn't find anything to use apart from the fundamental theorem of arithmetic. Here is my proof : Let $a,b \in N$ Suppose $a^5 | b^5$ Let $S = \{ \text{ n is prime } , n | a \lor n | b \} $ $ ...
0
votes
1answer
28 views

$\operatorname{lcm}(a,b) = c$ and $\gcd(a,b) = d$ => $\operatorname{lcm}(\frac{a}{d},\frac{b}{d}) = \frac{c}{d}$ in a Euclidean domain or PID

I know that in an integral domain $c=\operatorname{lcm}(a,b)$ if and only if $a\mid c, b\mid c$ and if there exists $c'$ such that $a\mid c', b\mid c'$ then this implies that $c\mid c'$. And ...
3
votes
3answers
403 views

Diophantine equation $ax + by = c$ has an integer solution $x_0, y_0$ if and only if $\gcd(a,b)|c$

Let $a,b,c$ be positive integers. Verify that Diophantine equation $ax + by = c$ has integer solution $x_0, y_0$ if and only if $GCD(a,b)|c$. Attempt Diophantine $ax + by = c$ has integer solution ...
4
votes
1answer
66 views

Finding missing digits in factorials

14!=871a82b1200 without working out 14!, find a and b I think it has something to do with maths rules regarding 9 or 3 (the digits adding up to either of those numbers) but not entirely sure!
1
vote
1answer
33 views

Divisibility problem using Wilson's theorem: $4(p-3)! + 2$ is divisible by $p$

Prove that $4(p-3)! + 2$ is divisible by $p$, where $p$ is an odd prime. Use Wilson's theorem. I am having trouble trying to bring it in the form where Wilson's theorem can be applied. Any help ...
0
votes
0answers
39 views

Put this word problem into math terms: A man goes to a stream…

A man goes to a stream with an 18-pint container and a 26-pint container. Using only these two containers: a) How does he get 2 pints of water into the larger container? b) What are all the ...
1
vote
3answers
85 views

Prove for positive integers a,b,c and d (where b does not equal d), if gcd(a,b) = gcd(c,d) = 1, then a/b + c/d is not an integer

I understand that if gcd(a,b) and gcd(c,d) = 1, at least one number in each pair is a prime or is 1. As for after that, I'm totally stumped, could I get some tips, clues, help?
2
votes
1answer
22 views

Prove that for positive integers a, b, c, and d such that b != d, if gcd(a, b) = gcd(c, d) = 1 then a/b + c/d is not an integer. [duplicate]

I attempted this by assuming that a/b + c/d is an integer and coming to a contradiction, but I got stuck. Any hints?
2
votes
1answer
120 views

If $m,n\in \mathbb N$ and $n>m$, prove that $\text{lcm}(m,n)+\text{lcm}(m+1,n+1)>\frac{2mn}{\sqrt{n-m}}$.

Where $\text{lcm}$ is the least common multiple. I've changed it to: $$\frac{mn}{\gcd(m,n)}+\frac{(m+1)(n+1)}{\gcd(m+1,n+1)}>\frac{2mn}{\sqrt{n-m}}$$ Can't see how to continue. Is there a way to ...
6
votes
2answers
446 views

Range of $ax+by$ where $\gcd(a,b)=1$

How to show that range of $ax+by$ is $\mathbb{Z}$ if $\gcd(a,b) = 1$. We can easily prove it if we can show that there exists some $x$ and $y$ such that $ax+by=1$. This could be showed by using ...
8
votes
2answers
807 views

Proof by induction on Fibonacci numbers: show that $f_n\mid f_{2n}$

I was studying Mathematical Induction when I came across the following problem: The Fibonacci numbers are the sequence of numbers defined by the linear recurrence equation- $f_n = f_{n-1} + ...
3
votes
2answers
133 views

Prove the $n$th Fibonacci number is the integer closest to $\frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^n$

Prove that the $n$th Fibonacci number $f_n$ is the integer that is closest to the number $$\frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^n.$$ Hi everyone, I don't really understand the ...
0
votes
0answers
48 views

Prove that $\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1$ [duplicate]

Prove that $\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1$ Hints- $1$. Use Euclids Lemma $2$. $2^a=2^{a\%c}\mod (2^c)-1$ $3$. If $a=q\cdot b+c$ then $2^a=(2^c)^q\cdot 2^r$
2
votes
2answers
203 views

If $ar + bs =1$, then $\gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1$

Here's the question: Let $a$ and $b$ be integers such that $\gcd(a,b) = 1$. Let $r$ and $s$ be integers such that $$ar + bs =1.$$ Prove that $\gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1$. I was stuck ...
2
votes
1answer
233 views

If $\gcd(\gcd(a, b),\gcd(a, c))=1$, then $\gcd(a, bc) = \gcd(a, b) \cdot \gcd(a, c)$

Let $a, b$ and $c$ be integers. Prove that if $\gcd(a, b)$ and $\gcd(a, c)$ are coprime, then $\gcd(a, bc)$ = $\gcd(a, b) · \gcd(a, c)$ I am stumped in this problem. Can anybody clarify me what ...
2
votes
2answers
109 views

If $\gcd(a, b) = 1$, then $\gcd(ab, c) = \gcd(a, c) \cdot\gcd(b, c)$

How can I prove that if $\gcd(a, b) = 1$, then $\gcd(ab, c) = \gcd(a, c) \times \gcd(b, c)$? By eea there exists $ax+by=1$ from $\gcd(a,b)=1$ so a and be are co-primes there also exists $dk=a$ and ...
0
votes
1answer
58 views

Arithmetic mean 6 times greater than GCD?

I am not sure how to find an answer to this question. Is there a way to solve it without simply trial and error? Do there exist ten distinct positive integers such that their arithmetic mean is (a) ...
2
votes
9answers
86 views

Prove that if $a, b$ are any positive integers $>1$, then either $a$ or $b$ or $a+b$ or $a-b$ is divisible by 3.

I checked all the integers from $1$ to $1000$ manually, I don't know exactly how to prove this but any simple and easy proof would be appreciated. Thanks.
1
vote
1answer
72 views

If an integer divides $(x-a)$ and $f(x)$ then it divides $f(a)$

Prove that if $n\, |\, (x-a)$ and $n \, | \, f(x)$ then $n \, | \, f(a)$ for a polynomial $f$. It is true if $\operatorname{deg}(f)=1$ or $2$, but what for greater degree of $f(x)$? I don't know ...
3
votes
2answers
64 views

GCD of many numbers

Given $a_1,...,a_n$ $gcd(a_1,...,a_n) = b$ I need to find $i$, so if i apply euclids algorithm to $(a_1,a_i)$, i end with $(0,b)$ or $(b,0)$.
0
votes
1answer
36 views

How does author reach step of $sa + tm \equiv 1 \pmod m$?

This is a proof of a theorem from my book, Discrete Mathematics and its Applications Theorem 1 If $a$ and $m$ are relatively prime integers and $m>1$, then an inverse of $a$ modulo $m$ ...
2
votes
4answers
52 views

How does one show that for $k \in \mathbb{Z_+},3\mid2^{2^k} +5$ and $7\mid2^{2^k} + 3, \forall \space k$ odd.

For $k \in \mathbb{Z_+},3\mid2^{2^k} +5$ and $7\mid2^{2^k} + 3, \forall \space k$ odd. Firstly, $k \geq 1$ I can see induction is the best idea: Show for $k=1$: $2^{2^1} + 5 = 9 , 2^{2^1} + ...
0
votes
2answers
52 views

Why doesn't x/0 = ±∞ [duplicate]

I was watching a video on numberphile about dividing by 0 and It said that x/0=Undefined or Error since it could be + or - ∞. ...