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)

5
votes
8answers
115 views

Prove with induction that $11$ divides $10^{2n}-1$ for all natural numbers.

$$10^{2(k+1)}-1 = 10^{2k+2}-1=10^{2k}\cdot10^{2}-1$$ I feel like there's something in that last part that should make it work, but I can't grasp it. Am I missing something obvious? Am I going in the ...
0
votes
1answer
38 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
46 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 ...
1
vote
1answer
24 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
37 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
70 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.
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 ...
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?
5
votes
6answers
119 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
0answers
31 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 ...
2
votes
2answers
34 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 ...
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
3answers
183 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
53 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 ...
2
votes
5answers
90 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.
1
vote
2answers
53 views

Prove that 100…500…1 (100 zeros in each group) is not a perfect cube?

How can i prove that 100...500...1 [100 zeros in each group ( ... is 100 zeros)]is not a perfect cube? I tried symmetric features of the number but could not figure out anything related.any ideas ...
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: ...
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$, ...
1
vote
5answers
103 views

Prove that $n^3+2$ is not divisible by $9$ for any integer $n$

How to prove that $n^3+2$ is not divisible by $9$?
-1
votes
3answers
44 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?
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 ...
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
98 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
1answer
54 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}$ .
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 ...
2
votes
2answers
21 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 \} $ $ ...
3
votes
3answers
93 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. ...
1
vote
1answer
28 views

Division rules for other number systems?

How could we make the same division rules for other number systems, like in our decimal system: a number is divisible with 2 if it's last digit is 0,2,4,6,8, by 3 if the sum of digits is divisible ...
0
votes
1answer
27 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 ...
4
votes
1answer
64 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!
2
votes
1answer
32 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
1answer
31 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
37 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 ...
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?
6
votes
4answers
144 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
9answers
84 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.
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) ...
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)$.
2
votes
4answers
51 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 - ∞. ...
1
vote
2answers
22 views

Proof dealing with greatest common divisors

I'm working on a proof which concludes that if $a\equiv b (mod\ m)$ then $gcd(a,m) = gcd(b,m)$ I know that we can rewrite the congruence as $km = a-b$ for some $k \in \mathbb{Z}$ I rearranged the ...
1
vote
3answers
82 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?
1
vote
3answers
33 views

Prove for integers a, b, and c, if gcd(a, b) = 1, a|c, and b|c then ab|c

Prove for integers $a$, $b$, and $c$, if $\gcd(a, b) = 1$, $a|c$, and $b|c$ then $ab|c$. Part b of this question is: "Is the converse true? Prove or disprove accordingly?" Hey, so I've been drawing ...
3
votes
4answers
89 views

If gcd$(a,b) = 1$, then I want to prove that $\forall c \in \mathbb{Z}$, $ax + by = c$ has a solution in integers $x$ and $y$.

If gcd$(a,b) = 1$, then I want to prove that $\forall c \in \mathbb{Z}$, $ax + by = c$ has a solution in integers $x$ and $y$. This is what I was attempting or trying: Let $d =$ gcd$(a,b)$. $d|a ...
0
votes
0answers
18 views

GCD and fraction problem

If x/y = 1/a + 1/b + 1/c and GCD of a , b and c is 9 then find a) minimum of x and y which do not cause x/y repeating decimal b) the best of x and y that cause x/y nearly to 3/10 many ...
2
votes
2answers
49 views

Find all numbers of form $10^k+1$ divisible by $49$

Basically, I've tried to take mods, and it hasn't been very successful. Also, if it helps, I noticed that the sequence can be recursively written as $a_{n+1}=10a_n-9$, starting with $a_1=11$.