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
44 views

Show that if $p\mid m^2$ then $p \mid m$ and hence $p^2 \mid m^2$

Show that if $p\mid m^2$ then $p \mid m$ and hence $p^2 \mid m^2$ I don't understand what is being asked of me. I thought this question was asking if $p$ divides $m^2$, then $p$ divides $m$, and ...
2
votes
2answers
85 views

Divisibility of sum of two numbers by $24$.

Let $m$ and $n$ be natural numbers such that $(mn + 1)$ is divisible by $24$. Then $m + n$ is divisible by: $2$ $3$ $8$ $12$ $24$ All of the above The answer given is 6. (all of the above). ...
4
votes
1answer
45 views

Prove that $2^{4n}+1$ cannot be a prime if $3|n$

$2^{4n}+1$ cannot be a prime if $3|n$ and $n>0$ My Try: $$2^{12k}+1\equiv (-1)^{3k}+1 \equiv0\pmod{17}$$ So it divisible by $17$ for odd $k$. But how to complete the proof?
0
votes
1answer
36 views

Polynomial long division modulo 7,

I need to determine the quotient and remainder using polynomial long division in $Z_7[x]$. I'm not sure how to tackle it with the polynomials given, and I'm growing frustrated by it. I need to divide ...
12
votes
3answers
343 views

Mental Primality Testing

At a trivia night, the following question was posed: "What is the smallest 5 digit prime?" Teams (of 4) were given about a minute to write down their answer to the question. Obviously, the answer is ...
2
votes
1answer
40 views

Prove that $[(a|b)\land(c|d)]\Longrightarrow ac|bd;\, a|b\Longrightarrow ac|bc;\, ac|bc\Longrightarrow a|b.$

Prove that: $$(a): [(a|b)\land(c|d)]\Longrightarrow ac|bd;$$ $$(b): a|b\Longrightarrow ac|bc;$$ $$(c): ac|bc\Longrightarrow a|b.$$ Proof: (a) By definition of divisibility, ...
8
votes
4answers
121 views

Show that $15\mid 21n^5 + 10n^3 + 14n$ for all integers $n$.

I'm not sure if it's correct, but what I have so far is; $$21n^5 + 10n^3 + 14n ≡ (1 + 0 - 1) ≡ 0 \mod 5$$ but I'm having trouble solving it in $\bmod 3$. I have: $$21n^5 + 10n^3 + 14n ≡ (0 + (?) + ...
0
votes
1answer
28 views

Trivial and nontrivial GCD of polynomials

What is the difference between trivial and non-trivial GCDs of two polynomials: $f,g$ where $f,g \in Q[x]$? I know if $f,g \in Z[x]$, the only non-trivial GCD is 1, and everything else is trivial. ...
0
votes
1answer
47 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
50 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 ...
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
88 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
156 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
157 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
125 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
190 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
56 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 ...