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

Generalized Fibonacci Sequence

I'm having trouble with a problem I encountered while studying Number Theory. This problem comes from the book Number Theory by George E. Andrews. It defines a generalized Fibonacci sequence $F_1$, ...
1
vote
2answers
52 views

Divisibility for 7

I have seen other criteria for divisibility by 7. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. 323) is interesting, but could not prove it. Let $n = ...
-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
66 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$ ...
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 ...
0
votes
2answers
25 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: ...
2
votes
2answers
96 views

Ring such that $q^2\mid p^2$ does not imply $q\mid p$?

Let $R$ be a commutative ring with $1$ and suppose $q^2\mid p^2,$ for $p,q \in R$. Unless $R$ is a UFD, I don't believe I can conclude that $q\mid p,$ but I would like to know a concrete ...
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 ...
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
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 ...
0
votes
2answers
23 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 ...
0
votes
1answer
36 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 ...
-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 $ ...
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.
1
vote
1answer
60 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 ...
3
votes
1answer
70 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 = ...
3
votes
5answers
578 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 ...
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 ...
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 : ...
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
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 ...
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 ...
6
votes
1answer
47 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
33 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 ...
2
votes
1answer
18 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
62 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 ...
8
votes
7answers
804 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$? ...
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 ...
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 ...
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 ...
0
votes
2answers
63 views

Prove or disprove this implication

Prove or disprove: If $x, a, b > 0$ are integers such that $$\gcd(x-a, x+b) = 1\ \ \mbox{and}\ \ \gcd(2x-a, x+b) > 1,$$ then $$a+b = x.$$
2
votes
1answer
44 views

$[n,n+1]=\text{ ??????}$

I know the answer is $n(n+1)$, but I'm having trouble formulating an argument. I know by the definition, if I let $h=[n,n+1]$ $$h=nk_1, h=(n+1)k_2$$ $$nk_1=(n+1)k_2$$ ...
0
votes
1answer
24 views

Prove superpolynomial growth rate [duplicate]

Let $p(n)$ be the number of partitions of $n$. Prove that growth rate of $p(n)$ is superpolynomial, meaning that for every given $k$ there is $p(n)= \omega (n^k)$.
1
vote
1answer
21 views

Find highest power of 2 that divides $3^{2^k}-1$

I am trying to find highest power of 2 that divides $3^{2^k}-1$ but I have no idea where to start - could you give me any hint?
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
1answer
17 views

Modified division, hyperreal numbers and transfinite derivatives

Suppose we are shooting from a cannon and measuring the speed of the projectile. The shorter period of time it takes for the projectile to reach the target, the faster it is. If the projectile hits ...