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)

2
votes
2answers
65 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. ...
-5
votes
1answer
65 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
31 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
84 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). ...
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 ...
0
votes
1answer
27 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 ...
3
votes
1answer
77 views

Values of $\gcd(a-b,\frac{a^p-b^p}{a-b} )$

I don't know how to prove the following result. Let $p$ be a prime number and let $a,b \in \mathbb Z$ such that $\gcd(a,b)=1$ Then $\gcd (a-b,\frac{a^p-b^p}{a-b}) = 1 $ or $ p $ (gcd should be ...
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 ...
4
votes
1answer
41 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?
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 ...
2
votes
4answers
53 views

Proving that if $8\mid (n^2+2n)$ then $2\mid n$

Let $n\in \mathbb N$ prove that if $8\mid (n^2+2n)$ then $2\mid n$. From the given, there exists $k\in \mathbb N$ such that $8k= (n^2+2n)$, take $k=1$, and we get $2\cdot 4 = n(n+2)$. Now my ...
2
votes
1answer
38 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
3answers
141 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.
0
votes
1answer
25 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
41 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
43 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 ...
2
votes
1answer
36 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
0answers
50 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 ...
0
votes
1answer
34 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 ...
1
vote
1answer
20 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 ...
3
votes
2answers
50 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.
3
votes
3answers
87 views

Let $a,b$ be positive integers such that $a\mid b^2 , b^2\mid a^3 , a^3\mid b^4 \ldots$ so on , then $a=b$?

Let $a,b$ be positive integers such that $a\mid b^2 , b^2\mid a^3 , a^3\mid b^4 \ldots$ that is $a^{2n-1}\mid b^{2n} ; b^{2n}\mid a^{2n+1} , \forall n \in \mathbb Z^+$ , then is it true that $a=b$ ?
11
votes
7answers
986 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 ...
6
votes
3answers
78 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
6answers
154 views

Proof: $\;n^2\;$ is even if and only if $\;n\;$ is even.

Please help how would you go about doing this? I'm studying for a final. This is on a study guide. I'm having a lot of trouble with this class. Prove that $n^2$ is even if and only if $n$ is even. ...
3
votes
2answers
1k views

Smallest possible integer for when $\dfrac{x}{10}$ leaves a remainder of 9 and so on

I'm in 8th grade and my geometry teacher recommended that I read the art of problem solving. So I did and I have now read the chapter called "Integers". I am now doing some of the problems in the ...
3
votes
6answers
64 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$.
2
votes
0answers
282 views

Prime numbers with binomial coefficients

Let $p$ be an odd prime and $n$ a positive integer. Prove that $p+1$ divides $n$ if and only if $$\sum_{k\equiv j\pmod{p-1}}^n\binom{n}{k}(-1)^{\frac{(k-j)}{p-1}}\equiv 0 \mod p$$ for every $$j\in ...
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 ...
0
votes
1answer
50 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 ...
11
votes
1answer
149 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
vote
1answer
32 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 ...
-1
votes
1answer
46 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
5
votes
8answers
122 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 ...
6
votes
3answers
113 views

Prove that, $(2\cdot 4 \cdot 6 \cdot … \cdot 4000)-(1\cdot 3 \cdot 5 \cdot …\cdot 3999)$ is a multiple of $2001$

Prove that the difference between the product of the first 2000 even numbers and the first $2000$ odd numbers is a multiple of $2001$. Please show the method. I have started with the following ...
1
vote
3answers
52 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 ...
0
votes
0answers
14 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
41 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 ...
2
votes
1answer
17 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 ...
1
vote
1answer
71 views

Use the second isomorphism theorem to conclude that $\gcd(a,b)\text{lcm}(a,b)=ab$

Use the second isomorphism theorem to conclude that $\gcd(a,b)\operatorname{lcm}(a,b)=ab$; that is, the product of the greatest common divisor and the lowest common multiple of $a,b$ is equal to ...
5
votes
1answer
94 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$.
3
votes
1answer
57 views

Prove $\forall n\geq 2,n\in\mathbb{Z}$, $(n+1)\mid(n^3+1)$

Question: Prove $\forall n\geq 2,n\in\mathbb{Z}$, $(n+1)\mid(n^3+1)$ I know that it is possible to solve by factoring $n^3+1$ and showing that $n+1$ is a multiple, but I would like to show this via ...
1
vote
4answers
112 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 $$
1
vote
5answers
105 views
0
votes
1answer
39 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 ...
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 ...