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)

13
votes
4answers
1k views

Is there a sequence of 5 consecutive positive integers such that none are square free?

Is there a sequence of 5 consecutive positive integers such that none are square free? A number is square free if there is no prime number p such that $p^2 \mid n$ What I've tried doing so far is to ...
0
votes
3answers
154 views

The largest number that will perfectly divide $101^{100}–1$ [closed]

The largest number amongst the following that will perfectly divide $101^{100}–1$ is: A. $100$ B. $10,000$ C. $100^{100}$ D. $100,000$ Can someone please answer this question. Thanks in advance.
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 ...
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.
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 ...
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
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 ...
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$.
11
votes
7answers
1k 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 ...
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 ...
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 ...
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
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 ...
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 ...
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 ...
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$.
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 $$
5
votes
8answers
156 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
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 ...
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 !
0
votes
2answers
52 views

If $a=b+c$ then $(a,b)=(a,c)=(b,c)$

If $a=b+c$ then $(a,b)=(a,c)=(b,c)$ I was thinking of writing the Euclidean algorithm \begin{align*}a &= b\cdot 1+c\\ b &= c\cdot (-1) + (b+c)\\ c &= a \cdot 1 + ...
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.
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
0answers
109 views

Automata to detect numbers divisible by $7$

I have a task and I really have no idea how to solve it. Build deterministic finite automata such that it can detect numbers divisible by $7$. So our alphabet is $\left\{0,1,2,3,4,5,6,7,8,9\right\}$ ...
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?
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
0answers
34 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
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 ...
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$.
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
5answers
119 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
55 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
42 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
46 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
325 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
106 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$?
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 ...
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
100 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
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}$ .
1
vote
2answers
55 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
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 \} $ $ ...