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)

1
vote
1answer
38 views

For what positive integers is this number-theoretic equation true?

For what odd (positive) integers $x$ is this number-theoretic equation true? $$\gcd(x^2, \sigma(x^2)) = 2x^2 - \sigma(x^2)$$ Here, $\gcd(a, b)$ is the greatest common divisor of $a$ and $b$, and ...
1
vote
2answers
36 views

Show that if $\gcd(r,s_1) =\gcd(r,s_2) = 1$, then $\gcd(r,s_1s_2) = 1$

Never mind the question. I want to try to solve that on my own. What I want to understand is how this: "Hint. $1 = ar + bs_1,\ 1 = ar + bs_2$" relates to solving it. I'm a little confused by this ...
4
votes
5answers
94 views

Prove by induction that $n^3 + 11n$ is divisible by $6$ for every positive integer $n$.

Prove by induction that $n^3 + 11n$ is divisible by $6$ for every positive integer $n$. I've started by letting $P(n) = n^3+11n$ $P(1)=12$ (divisible by 6, so $P(1)$ is true.) Assume $P(k)=k^3+11k$ ...
1
vote
2answers
28 views

Proving divisibility of $a^3 - a$ by $6$

As part of a larger proof, I need to show why $a^3-a$ is always divisible by $6$. I'm having trouble getting started.
-5
votes
1answer
68 views

Division by zero after removing factor. [duplicate]

I know that anything divided by zero is undefined and I understand why. However, I have just discovered this sum, and it confused me greatly. Could anyone explain what is going on here: $$x-x=0$$ ...
1
vote
3answers
33 views

If $x,y$ are integers greater than $1$ and $n$ is a positive integer such that $2^n + 1=xy$ , $\exists 1< a<n$ such that $2^a|x-1$ or $2^a|y-1$?

If $x,y$ are integers greater than $1$ and $n$ is a positive integer such that $2^n + 1=xy$ , then is it true that either $2^n|x-1$ or $2^n|y-1$ ? I have only been able to observe that both $x,y$ are ...
0
votes
1answer
31 views

Simple number theory

I'm new in number theory and I was asked this question: For the number $N$ output the amount of numbers $M$, such that $1 \le M \le N$, $\gcd(M, N) \ne 1$ and $\gcd(M, N) \ne M$. How can i solve it?
2
votes
2answers
73 views

Find the gcd of two polynomials: $f(x) = x^4+1$ and $g(x)=x^2-1$ using the Euclidian algorithm.

I need to find the gcd of two polynomials: $f(x) = x^4+1$ and $g(x)=x^2-1$ using the Euclidian algorithm. Wolfram shows that the gcd is equal to $1$, but for some reason I don't get the same answer. ...
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
86 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
47 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
40 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
348 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
33 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
49 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
157 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
53 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
56 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.
2
votes
1answer
37 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
99 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
66 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
160 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
56 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
17 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
56 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
20 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
98 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
160 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
41 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
103 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
112 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
25 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 ...