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
0answers
15 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 ...
0
votes
7answers
77 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
8 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
87 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
93 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
29 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
40 views

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

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
72 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
29 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
26 views

Divisibility of Integers Question [on hold]

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
489 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$ [on hold]

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
36 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
84 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
48 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
41 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 ...
2
votes
3answers
371 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
18 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
84 views
+50

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} ...
2
votes
4answers
52 views

system of congruence - my approach

We have: $$k^3 + l^3 \equiv 0 \pmod{17}\\ k^2 + l^2 \equiv 0 \pmod{17} $$ And I get: $$k = 17n+r_k\\ l = 17m+r_l$$ And I analyzed possible rests respect to system of congruences. My result is: $$ ...
1
vote
5answers
59 views

If $p^2\,$is divisible by 3, why is p also divisible by 3? [duplicate]

I came across this in proving that the $\sqrt{3}$ is irrational
0
votes
2answers
24 views

Is this a valid proof technique regarding the divisibility of numbers?

Claim: All numbers of this sequence are relatively prime to one another: $$2^1 + 1, 2^2 + 1, 2^4 + 1, \ldots, 2^{2^n} + 1$$ So, I decided to include $2^0 + 1$. That way: Base case: $$2^0 + 1 ...
0
votes
1answer
23 views

number system and divisibility

could anyone please find a solution to that problem: $b$,$c$,$d$ are consecutive even integers such that $2\lt b \lt c \lt d$. what is the largest positive integer that MUST be a divisor of $bcd$?
2
votes
1answer
44 views

Determine the divisibility of a given number without performing full division

My question is slightly more complicated than what's implied on the title, so I will start with an example. Given any number $N$ on base $10$, we can easily determine whether or not $N$ is divisible ...
2
votes
0answers
18 views

How to know if the number of divisors in a determined range for a number is odd or even [duplicate]

I would like to know if the number of divisors for the number in a determined range is odd or even without counting the divisors, I think the question is a little tad fuzzy, thus, I will supply the ...
4
votes
1answer
65 views

Factors of integers of the form $2^n-1$

I came across a problem where i had to tell the number of divisors of $2^i-1$ which are of the form $2^j-1$. I saw many contestants using the fact that if $i$ is divisible by $j$ then $2^i-1$ is ...
2
votes
0answers
56 views

How to find the approximate basic frequency or GCD of a list of numbers?

I could't actually summarize the question in the title, so I'll explain my situation. I want to tell the integer numbers which act as the best approximate basic frequencies of a list of real numbers: ...
0
votes
2answers
75 views

Prove that if $p$ is prime, and $a^2=b^3$

I have an exercise that I don't know how to solve. I tried to solve it in many ways, but I didn't get any progress in proving or disproving this... The exercise is: Prove or disprove: if $p$ is a ...