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
2answers
24 views

Divisibility crieteria

This is a follow-up question. The problem is: Given two natural numbers, $m$ and $n$, and $n \vert m^2$. Find necessary and sufficient conditions for $n \vert m$. Here are what I find: ...
21
votes
5answers
9k views

If $a^2$ divides $b^2$, then $a$ divides $b$

Let $a$ and $b$ be positive integers. Prove that: If $a^2$ divides $b^2$, then $a$ divides $b$. Context: the lecturer wrote this up in my notes without proving it, but I can't seem to figure out ...
-1
votes
2answers
17 views

Solution for trinomial divided by binomial equation

I have the following equation to solve. I know that the answer is -5, I made several attempts at this, and arrive at a different answer. My first thought was to factor out the trinomial, but that ...
1
vote
3answers
65 views

Prove that $17$ divides $9a + 5b$

So, according to the book, for all $a, b, c$ that are elements of integers, it holds that $a|b$ implies $a|bx$ for all $x$ that is an element of integers. In other words it works for all ARBITRARY $x$ ...
2
votes
2answers
140 views

Prove that every odd natural number divides some number of the form $2^n - 1$ [duplicate]

Suppose that $m$ is an odd natural number. Prove that there is a natural number $n$ such that $m$ divides $2^n -1$. I have absolutely no idea how to tackle this; any assistance would be welcome.
1
vote
2answers
68 views

Find the next divisor without remainder

I divide a value and if the remainder is not 0 I want the closest possible divisor without remainder. Example: I have: $100 \% 48 = 4$ Now I am looking for the next value which divide 100 wihtout ...
1
vote
3answers
39 views

If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$

As stated in the title, the problem to prove is Let $a,b,c \in \mathbb{Z}$. If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$. I think I've proved it, but I would like a second opinion. Here ...
1
vote
1answer
30 views

Polynomial and its derivative have a common factor?

When is $gcd(p(x),p'(x))\ne 1$ where $p(x)$ is a polynomial? That is when does the derivative of a polynomial and the polynomial has a common factor? By when i mean some condition for the ...
4
votes
4answers
166 views

Inequalities, when does the sign change here?

I have encountered a problem with inequalities. I have been looking at examples provided by two websites which 'solve' inequalities, however when I try using my own method, the extremely simple ...
1
vote
4answers
50 views

Direct proof using modular arithmetic

Give a direct proof of $8\mid (3^n + 5^n)$ for all odd natural numbers. I know how to prove this by induction, I am not sure how to go about it using a direct proof. I would start by saying that ...
1
vote
1answer
126 views

Why isn't $1$ a superior highly composite number?

A superior highly composite number is a positive integer $n$ for which there is an $\epsilon>0$ such that $\dfrac{d(n)}{n^\epsilon} \geq \dfrac{d(k)}{k^\epsilon}$ for all $k>1$, where the ...
2
votes
0answers
24 views

Prove the congurence

I am looking for a proof of Gauss's generalization of Wilson's Theorem. Let $S$ be the set of all the integers which are less than and mutually prime to $n (>4)$ (not of the form $p^\alpha$, ...
0
votes
1answer
35 views

Parity of number of factors up to a bound?

Consider $b,n\in\mathbb{N}$ where $b\leq n$. We want to find the parity (ie. odd or even) of the number of divisors of $n$ that are $\leq b$. The question is to find a fast algorithm to find that ...
0
votes
1answer
77 views

Divisibility of huge numbers

Please help me to solve my homework ;) Prove that for any positive integer $n$ a square of rather big number divides even more huge number: $${\LARGE \left.\underbrace{33\dots 3}_{1\underbrace{00\dots ...
1
vote
0answers
46 views

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ primes. What are the first values of $U(n)$?

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ prime numbers (except for the first prime number: $2$). What are the first values of $U(n)$ up to ...
8
votes
7answers
801 views

Better Divisibility by 8

Everywhere I look, when you want to see if something is divisible by $8$ then you see if the last $3$ digits are divisible by eight. But how do you know if the last $3$ digits are divisible by $8$? ...
0
votes
2answers
22 views

Equation Theory: A polynomial with specific remainders when divided by specific divisors. What is the remainder when divided by BOTH divisors

Again, for my Equation Theory class, I have the subject question.$p(x)$ has a remainder of 3 when divided by $x-1$ and a remainder of 5 when divided by $x-3$. What is the remainder when $p(x)$ is ...
1
vote
0answers
32 views

Find the Conditions

Let $a, b, c, d, r, s \in \mathbb{N}$. Find the necessary and sufficient conditions under which $r \mid (a-b)$ and $s \mid (c-d)$ $\implies$ $\operatorname{lcm}$ $(r,s)\mid(ac-bd)$. A little ...
1
vote
2answers
79 views

Solving $a^2+b^2\equiv 0$ mod $c$ for distinct integers $a,b,c$ constrained between two consecutive squares

Show that for any natural number $n$, between $n^2$ and $(n+1)^2$ one can find three distinct natural numbers $a,b,c$ such that $a^2+b^2$ is divisible by $c$. A friend and I found a general case that ...
-1
votes
4answers
50 views

How many divisors are there in 2015, that is d(2015)? [closed]

This is the question raised in our class to check our understanding in divides.
1
vote
1answer
46 views

Question in elementary number theory

I have a question. Suppose that $a$ and $b$ are two natural numbers so that $ a<b$ and $ a\nmid b$. Put $ d=ka$, where $ k\not=0,1,t\dfrac{b}{\gcd(a,b)}$, for $ t\geq 1$. I want to prove that $ ...
1
vote
1answer
58 views

Characterizing the primes which don't divide any Pell-Lucas number(s)

For integer $n$, let $P_n$ be a Pell number, and $Q_n$ its companion. Is there a characterization of the prime numbers $p$ which don't divide any $Q_n$? By brute-force search, I found that this ...
0
votes
5answers
40 views

How do you prove this divisibility?

If $n$ is any natural number, prove that $3\mid 2^{2^n}-1$ is true. I can't find out how to do it. Thanks.
3
votes
5answers
576 views

The sum of three consecutive cubes numbers produces 9 multiple

I want to prove that $n^3 + (n+1)^3 + (n+2)^3$ is always a $9$ multiple I used induction by the way. I reach this equation: $(n+1)^3 + (n+2)^3 + (n+3)^3$ But is a lot of time to calculate each ...
3
votes
1answer
69 views

Probability that two random integers have only one prime factor in common

The probability that two integers picked at random are relatively prime is known to be $1/\zeta{(2)}=6/\pi^2\approx0.607927...$. Generalizing, the probability that $n$ random integers have $\gcd=1$ is ...
0
votes
3answers
28 views

Help with understanding definition of divisibility in this case.

I have a proof that shows that if $5 \mid xy$ then $5 \mid x$ or $5 \mid y$. It's pretty clear to me that I can just say that suppose $5 \mid x$, then $x=5a$, where $a$ is an integer. then $xy = ...
0
votes
1answer
68 views

Divisibility of a number by $(4k+3)$ in minimum time

Please suggest any algorithm with minimum time complexity to check whether a number $n$ is divisible by at least one $(4k+3)$ where $k>0$ is integer and $(4k+3)\le n$?
2
votes
5answers
67 views

Proof regarding divisibility

if $n\in\mathbb{Z}$, then $4$ does not divide $(n^2 - 3)$ I'm not sure how to approach this question, I know how to do questions that involve proving that it does divide but I'm unsure of how to do ...
4
votes
1answer
236 views

The product of any three consecutive natural numbers is divisible by 9.prove or find a counterexample

can anyone give me feedback on my solution false counterexample: n(n+1)(n+2) let n= 1 1(2)(3) =6 is not divisible by 9 is this correct?
0
votes
1answer
31 views

How to get all divisors of an integer using only pen & paper

Is there any fast approach to get all divisors of an integer by only using pen & paper?
0
votes
0answers
74 views

Counting maximum moves

Given two arrays, each of size N denoted by A1,A2...AN and B1,B2...BN. Let us maintain two sets S1 and S2 which are empty initially. In one move ,Pick a pair of indexes (i, j) such that : ...
0
votes
1answer
42 views

Polynomials - getting wrong answer using Euclidean algorithm

I am finding the GCD of $a = x^3 + 11/3x^2 + 17/4x + 3/2$ and $b = 3x^2 + 22/3x + 17/4$ using the Euclidean algorithm. So I divide $a/b$ and get $q$ and $r$ such that $a = qb + r$. Then, according to ...
2
votes
2answers
60 views

How to divide a number by $2$ numbers?

I have to distribute newspapers, and the printing company gives it to me in bundles of $15$ and $25$, now if a store wants $115$ I will have to send them $4 \times 25$ and $1 \times 15$, or if they ...
0
votes
2answers
355 views

Finding Coprime triplets

Given a sequence a1, a2, ..., aN. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(ai, aj, ak) = 1. Here GCD stands for the Greatest Common Divisor. Example : Let N=4 ...
0
votes
1answer
21 views

Position of switches based on divisibility

There is a set of $1000$ switches. Each has four different positions, called $A$, $B$, $C$, and $D$. When the position of any switch changes, it is only from $A$ to $B$, from $B$ to $C$, from $C$ to ...
0
votes
2answers
62 views

Find all values of for which the ratio is an integer

Find all values of $n$ for which, $$\dfrac{(\dfrac{n+3}{2}) \cdots n}{(\dfrac{n-1}{2})!}$$ is an integer. I have tried the problem for some primes. Each time it seemed true. But I still ...
5
votes
3answers
153 views

Prove $x^3-3x+4$ is irreducible in $\mathbb{Q}[x]$

I want to prove $x^3-3x+4$ is irreducible in $\mathbb{Q}[x]$. Eisenstein's criterion doesn't apply here, so I think the simplest method would be to use the Rational Roots Test, right? If I can use ...
6
votes
1answer
46 views

Sequences where each number is a divisor of one less than the next

Let $N,k$ be fixed. Call a sequence of positive integers $a_1,a_2,\dots,a_k$ good if for each $i$, $a_i$ is a divisor of $a_{i-1}-1$. Consider the set $$S = \{a_i : a_1,\dots,a_k \text{ is a good ...
2
votes
1answer
26 views

Group divisibility question

I have the following question which I can't make sense of, here is the entire question: If $G$ is a group, $b\in G, o(b)=k$ and $b^n = e$, show that $k|n$ What is $o(b)$? Please help.
1
vote
2answers
32 views

GCD question involving coprimes

How can I prove that if $\gcd(a, b) = 1$, then $\gcd(ab, c) = \gcd(a, c) \times \gcd(b, c)$? By eea there exists $ax+by=1$ from $\gcd(a,b)=1$ so a and be are co-primes there also exists $dk=a$ and ...
0
votes
1answer
17 views

Proving $k$ is a common divisor of $a$ and $b$ iff $k\,|\gcd(a,b)$ — converse

I'm currently trying to solve the converse of this statement is true after proving the normal version is true. If $k$ is a common divisor of $a$ and $b$, then $k \,| \gcd(a, b)$ So far I know the ...
1
vote
2answers
3k views

If $\gcd(a,b)=1$ and $a$ and $b$ divide $c$, then so does $ab$

Using divisibility theorems, prove that if $\gcd(a,b)=1$ and $a|c$ and $b|c$, then $ab|c$. This is pretty clear by UPF, but I'm having some trouble proving it using divisibility theorems. I was ...
2
votes
1answer
17 views

Questions relating to gcd

Assume a, b and c are positive integers. 1) Suppose that a | b. Show that gcd(a, c) ≤ gcd(b, c). 2) Suppose that a ≤ b. Is it necessarily true that gcd(a, c) ≤ gcd(b, c)? I'm having trouble with ...
0
votes
1answer
56 views

The binomial coefficients $\binom{n}{ p}$ are divisible by a prime $p$ only if $n$ is a power of $p.$

I'm looking for a "high school / undergraduate" demonstration for the: All the binomial coefficients $\binom{n}{i}=\frac{n!}{i!\cdot (n-i)!}$ for all i, $0\lt i \lt n$, are divisible by a prime $p$ ...
3
votes
1answer
61 views

If $k$ is an odd number then $3k^2 +16$ is not a perfect cube

I am pretty sure that the title is true. Could anybody please prove it? I am particularly interested in a proof that mostrly relies on divisibility.
0
votes
1answer
32 views

Finding greatest common divisor between two polynomials.

I have the following past exam question: Calculate $\operatorname{gcd}(x^3 + 2x^2 + 2,2x^2 + 1)$ in $\mathbb{F}_3$ Now I haven't encountered this sort of gcd before(usually I am trying to solve ...
1
vote
3answers
41 views

Prove that $(k.n)!$ is divisible by $(k!)^n$

Suppose $k,n$ are integers $\ge1$. Show that $(k.n)!$ is divisible by $(k!)^n$ I have simplified the problem and now, I need to prove that any $k$ consecutive integers is divisible by $k!$. However I ...
1
vote
5answers
60 views

$n \in \mathbb{N} \ 5|\ 2^{2n+1}+3^{2n+1}$

show for all $n \in \mathbb{N}$, $$5|\ 2^{2n+1}+3^{2n+1}$$ Indeed, we've to show that : $2^{2n+1}+3^{2n+1}=0[5] $ note that $2^{2n+1}+3^{2n+1}=2.4^n+3.9^n= $
1
vote
1answer
42 views

Prove that $f(n,p)$ is a non-square integer

Let, $$f(n,p)=(n+1)(n+2) \cdots (n+p-1)$$ Then show that $f(n,p)$ is a not a perfect square for all $n \in \mathbb{N}$ and for all odd primes $p$. Consider only the cases when ...
1
vote
2answers
35 views

Contrapositive proof using rule of divisibility

Suppose $x,y,z$ are integers and $x \neq 0 $ if $x$ does not divide $yz$ then $x$ does not divide $y$ and $x$ does not divide $z$. So far I have: Suppose it is false that $x$ does not divide $y$ and ...