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
4answers
31 views

The divisibility of the values of quadratic polynomials in $x$, for integer $x$

I would like to know method of finding validity of the statement by proofs. 1) $8$ does not divides $x^2 - 7$ for any integral value of $x$? 2) For any odd integer $x;$ the term $(x-1)^2$ is always ...
0
votes
3answers
39 views

Proof that the greatest common divisor of (a, a+2) is 2 if a is even and 1 if a is odd

Some help would be great on this, my teacher hasn't explained how to construct proofs to us, he just keeps doing them for us in class. I have at the beginning: Let a be even. Since the sum of two ...
0
votes
3answers
46 views

The only positive divisor of both $a$ and $a + 1 $ is $1$

Prove that if $a \in \mathbb Z$ then the only positive divisor of both $a$ and $a + 1$ is $1$. When I saw this statement I didn't understand it. The only way that I can see it being true is if a is a ...
1
vote
3answers
50 views

Part of a proof that the product of an odd and even integers is even

I'm practicing for a test on Monday and I'm trying to do some proofs - but I'm not entirely sure if this is sufficient enough for the question. "Prove that for all integers, m and n, if m is odd and ...
1
vote
3answers
92 views

Sum of the digits

Let $N$ be the greatest number that will divide $1305,4665$ and $6905$, leaving the same remainder in each case. Then what is the sum of the digits in $N$?
0
votes
1answer
52 views

Under what conditions can $a\sqrt{b} \pm c\sqrt{d}$ be written as $u+v\sqrt{w}$?

Let $a,b,c,d \ge 1$ be integers with $b$ and $d$ nonsquare and $a\sqrt{b} \ge c\sqrt{d}$. Now I have three related questions: Under what conditions can one find $u,v,w$ such that $a\sqrt{b} \pm ...
3
votes
1answer
47 views

Let a,b,c be integers. Prove that if a|c and b|c, then either a|b or b|a.

Let a,b,c be integers. Prove that if a|c and b|c, then either a|b or b|a. Any ideas? (Suggested proof by contradiction). Not really sure how to go about this.
0
votes
1answer
33 views

searching a number in 2D matrix

I was looking for algorithm on searching a number in a 2D matrix, with property that the matrix is sorted both row-wise and column-wise. Finally i came across, this link ...
-2
votes
1answer
29 views

Congruences and divisibility [on hold]

Prove that $11|\; 5^{99}+6^{99}$
1
vote
0answers
18 views

Sequence terms being divisible

Here's a question I would like hints for: The sequence ${x_n}$ is defined by $x_{n+2}=6x_{n+1}-9x_{n}$ for $n \geq 0$ where $x_0=3$ and $x_1=18$. What is the smallest $k$ such that $x_k$ is ...
0
votes
0answers
27 views

Changing the zero product property and defining division by zero [duplicate]

I know that defining division by zero is not possible because it violates the zero product property we define, that is, $0\times a=0$ for every $a$. I wonder whether we can somewhat circumvent and ...
1
vote
7answers
80 views

Prove by induction that $n(n+1)(n+5)$ is multiple of 3

$$n(n+1)(n+5) = 3d$$ I cannot figure out how to solve this homework question. A friend gave me a solution I couldn't make sense of, and I hope there's something easier out there. Also, what would be ...
1
vote
1answer
9 views

If $n \in \mathbb{N} - \{1\}$, $ a \in \mathbb{Z}$, and $gcd(a,n)=1$, show there is $1 \leq i<n$ with $n|(a^i -1)$.

If $n \in \mathbb{N} - \{1\}$, $ a \in \mathbb{Z}$, and $gcd(a,n)=1$, show there is $1 \leq i<n$ with $n|(a^i -1)$. So far I have shown that, if $gcd(a,n)=1$, then $gcd(a^j,n)=1$. I also have a ...
1
vote
2answers
92 views

How do you make the coefficients of the simple linear combination of the gcd positive?

I was trying to convert a simple linear combination (and gcd): $$gcd(a,b) = ax + by$$ To have positive coefficients. I did read the following here but didn't really understand it and was looking ...
6
votes
2answers
102 views

$\gcd(a,b)$ compared to $\gcd(3a,b)$

$\gcd(a,b)=\gcd(3a,b)$? They are obviously not equal in general, as $\gcd(ax, bx)=|x|\gcd(a,b)$.
0
votes
0answers
31 views

Linear polynomials relatively prime iff $ad-bc \ne 0$

Two nonzero polynomials $a+bx$ and $c+dx$ are relatively prime in $\mathbb{R}[x]$ if any only if $ad-bc \ne 0$. It's not too hard to show this on a case-by-case basis by enumerating each possible ...
0
votes
4answers
46 views

Prove that $2|(x^4-3) <=> 4|(x^2+3)$

Prove that $2|(x^4-3) <=> 4|(x^2+3)$ What i have right now is: Consider the case (=>): Since $x^4-3$ divides $2$ then, there must exist n belongs to integer, such that $n = \frac{x^4-3}{2}$ I ...
0
votes
2answers
23 views

Stuck with divisibility test in Permutations

How many 5 digit numbers can be formed using digits 0 to 7, divisible by 4, if no digit occurs more than once in a number. 1480 780 1360 1240 None Of These I could calculate the ...
1
vote
1answer
41 views

$x \rightarrow x^n$ is a group automorphism of a finite abelian group G [closed]

How do we prove that the map $\phi:G \rightarrow G$ defined by $\phi(x) = x^n$ for some $n \geq 0$ is a group automorphism of $G$ if $\gcd(|G|,n)=1$?
0
votes
3answers
50 views

If $a-b$ is a multiple of $c$, then $a^n - b^n$ is a multiple of $c$

So I'm stuck doing this problem. Since we have to use induction, I have gotten as far as the base step and then realized that I'm going about this wrong. Here's the problem: If $a, b, c \in ...
1
vote
4answers
73 views

Prove if $2\mid(x^2-1) $, then $4\mid(x^2-1)$

I have no idea where to start. Any hint(s) or suggestions? Prove if $2\mid(x^2-1) $, then $4\mid(x^2-1)$
0
votes
2answers
22 views

Proof of $g^a \equiv 1 \pmod{m}$ and $g^b \equiv 1 \pmod{m} \quad \implies \quad g^{\gcd(a,b)} \equiv 1 \pmod{m}$

I am trying to understand the following: $$g^a \equiv 1 \pmod m \quad \text{and} \quad g^b \equiv 1 \pmod{m} \quad \implies \quad g^{\gcd(a,b)} \equiv 1 \pmod{m}.$$ I have tried a few approaches, ...
4
votes
1answer
45 views

Is it true that the gcd of cubes is the cube of gcd?

Is it true that $\forall a,b\in \mathbb{Z}$, $\gcd(a^3, b^3)=\gcd(a,b)^3$? I cannot find a counterexample, nor have I been able to finish a proof. One thing I tried was: $\gcd(a^3, b^3)= \gcd(a^3, ...
0
votes
2answers
35 views

Divisors of numbers of the form $a^2+2b^2$ with $\gcd(a,b)=1$

Let's say I have a number $n$ which can be written as $a^2+2b^2$ for integers $a,b$. By Fermat/Euler/etc., I know that the primes dividing the squarefree kernel of $n$ cannot be congruent to $5$ or ...
0
votes
1answer
30 views

Formula for the floor of $n/2$, to be proved by induction

How do you compute this when the base case is all wrong?
0
votes
4answers
29 views

Divisibility of Integers Question [closed]

Prove the following: If $a|(b-1)$ and $a|(c-1)$, then $a|(bc-1)$.
0
votes
3answers
35 views

What is wrong with my algorithm for finding how many positive integers are divisible by a number d in range [x,y]?

I have been solving basic counting problems from Kenneth Rosen's Discrete Mathematics textbook (6th edition). These come from section 5-1 (the basics of counting), pages 344 - 347. This question ...
1
vote
1answer
41 views

Solving for a variable in an integer divisibility problem

Say I have a problem of the form Where , , and are known integers, is some unknown variable, and is an integer output. Is there an approach I could take to determine if there is some integer ...
4
votes
4answers
490 views

How many integers in the range [1,999] are divisible by exactly 1 of 7 and 11?

This is a question in Kenneth Rosen's Discrete Mathematics textbook 6th edition. I haven't had trouble with any other counting problems regarding "how many numbers in range [x,y] have divisibility ...
1
vote
1answer
27 views

GCD between a polynomial with terms of even degree and a polynomial with terms of odd degree.

We are given a polynomial $p(z)=a_0z^n+b_0z^{n-1}+a_1z^{n-2}+b_1z^{n-3}+\dots=P_1(z)+P_2(z)$, where $P_1(z)=a_0z^n+a_1z^{n-2}+\dots$, $P_2(z)=b_0z^{n-1}+b_1z^{n-3}+\dots$. Let ...
-1
votes
1answer
33 views

Each set of $n$ integers contains at least two items $x,y$ such that $n-1\mid x-y$ [closed]

Can we determine for which $n\in\mathbb{N}$ the statement in the title is true?
0
votes
0answers
9 views

determining no of divisor of quotient '$Q$'

i want to determine number of '$k$'($1 \leq k \leq n$) such that if i divide '$n$' with 'k' then quotient is '$Q$'. for example: $n=5$ and $Q=2$ then ans$=1$ because for only $k=2$ ,$ \frac{n}{k}=Q$. ...
0
votes
0answers
15 views

Problems on Divisability

Consider the following problem If $k-1$ divides $n-1$, $k(k-1)$ divides $n(n-1)$, $n = r$ mod $k$ Find the smallest value m>n such that $k-1$ divides $m-1$ and $k$ divides $m$
0
votes
0answers
33 views

Divisibility: if a|b and b|c, then a|(b+c)

So I'm unsure as to how to prove this: if $a|b$ and $b|c$, then $a|(b+c)$ I'm aware of the divisibility properties such as if $a|b$ then $b=ak$ for some integer $k$. I also know the Transitivity of ...
2
votes
4answers
39 views

If $c\mid ab$ and $\gcd(c,a)=d$, then $c\mid db$

I came across this problem in my number theory text and am having a bit of trouble with it: Prove if $c\mid ab$ and $\gcd(c,a)=d$, then $c\mid db$. Here's what I have so far: If $c\mid ab$, then ...
2
votes
2answers
25 views

Question about G.C.D.

Let, $$a_{n}=n^2+20$$ $$d_{n}=\gcd(a_{n},a_{n+1})$$ where $n$ is a positive integer. Find the set of all values attained by $d_{n}$ I tried, $d_{n}=\gcd(n^2+2n+21,n^2+20)$ ...
5
votes
1answer
85 views

If $a^n-1$ is divisible by $b^n-1$ for all $n$, then $a$ is a power of $b$

Let $a,b$ be natural numbers not equal to $1$ such that $\frac{a^n-1}{b^n-1}$ is natural for any natural $n$. Prove that $a=b^m$ for some natural $m$.
2
votes
2answers
146 views

A question on gcd :

Here's the question: Let $a$ and $b$ be integers such that $\gcd(a,b) = 1$. Let $r$ and $s$ be integers such that $$ar + bs =1.$$ Prove that $\gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1$. I was stuck ...
0
votes
1answer
53 views

Determine all the integer solutions to $23x + 39y = 2$

I would like to calculate all the solutions to this equation using Euclides' algorithm and linear combination after finding the GCD. I suppose it's easy, but I'm a beginner. $23x + 39y = 2$
0
votes
1answer
17 views

Simple problem of divisibility.

Given a number N, N <= 10 ^ 10 and given a integer d, also we are given an integer R we have to find integer L such that for every integer i from L to R the integer division (N / i) = d it is ...
0
votes
2answers
79 views

Prove that $6! \mid n(n+1)…(n+5)$ [closed]

Prove that for all $n \in \mathbb{Z}$, $6! \mid n\cdot(n+1)\cdots(n+5)$ using only criteria of divisibility (without using combinatorial arguments).
2
votes
0answers
33 views

Is there a cycle for modulo operation on a floor?

I have a floor $${\left\lfloor\frac{n}{i}\right\rfloor},$$ where i varies from 1 to n (n can be upto $10^{10}$), and there's another number given 'm' (m upto $10^{5}$). Does ...
0
votes
2answers
49 views

How many 4-digit numbers with $3$, $4$, $6$ and $7$ are divisible by $44$?

Consider all four-digit numbers where each of the digits $3$, $4$, $6$ and $7$ occurs exactly once. How many of these numbers are divisible by $44$? My attack: There are $24$ possible four ...
2
votes
3answers
45 views

How do I prove that numbers not divisible by 3 can be represented as 3x+1 or 3x-1?

I saw that some proofs used the fact that numbers not divisible by $3$ can be represented as $3x+1$ or $3x-1$. But how do I prove that it is true?
0
votes
1answer
42 views

If $n$ is a composite number, then $(7^n-1)/6$ is also composite

Let $n \ge 2$ and $a_n = \dfrac{7^n−1}{6}$. Prove that if $n$ is composite then $a_n$ is composite. I would normally prove something like this with induction but in this case I don't know how to ...
3
votes
3answers
377 views

Divisible by 19 Induction Proof

Prove by induction that for all natural numbers $n$, $\frac{5}{4}8^n + 3^{3n-1}$ is divisible by $19$. I'm running into trouble at the inductive part of the step, I am currently attempting to ...
1
vote
5answers
45 views

Not clear on what we mean with numbers with infinite digits

I am confused on a rather simplistic question. 1/3 = 0.333333333333 to infinity. So it has infinite digits. How is it possible to multiply such a number with another one and get a finite number? 6/3 = ...
3
votes
1answer
59 views

Greatest common divisor problem involving $a^p+b^p$ [closed]

Let $\gcd(a,b)=1$ for some $a,b\ \epsilon \ \mathbb{N}$. Prove that for any odd prime p: $$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1,~~~~ \text{or} ~~~p.$$
0
votes
0answers
19 views

Could you give a definition of what is a superior highly composite number using only words?

I know very well what is a superior highly composite number, but I would like to see how could we (roughly) define what is a superior highly composite number using only words (using no equations and ...
6
votes
0answers
116 views

Seeking help extending Vieta-jumping to higher powers

I am trying to prove the following conjecture. Conjecture. If $r > s \ge 1$ are relatively prime integers such that \begin{equation} (r-s)^4-1 \equiv 0\!\pmod{4r^2s}, \tag{1} \end{equation} ...