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
3answers
105 views

Prove or disprove $ p^{r+s}\mid q^{ke} - 1 \iff p^s \mid k$.

Let $p$ be an odd prime and $q$ be a power of prime. Suppose $e := \min\{\, e \in \mathbb{N} : p \mid q^e - 1 \,\}$ exists. Put $r := \nu_p(q^e - 1)$ (that is, $p^r \mid q^e - 1$ and $p^{r+1} \nmid ...
0
votes
2answers
52 views

a proof of contradiction

I am wondering whether the following is a valid proof?
10
votes
1answer
130 views

Does there always exist an even $m$ that is a multiple of exactly $n$ of the numbers $1$, $2$, …, $2n$?

Let $n>1$ be a positive integer. Then there exists a positive integer $m$ such that exactly half of the numbers $1$, $2$, $\ldots$, $2n$ divides $m$: one can take $m = (2n-1)!! = (2n-1) \times ...
0
votes
1answer
45 views

Question about $\gcd$

Theorem: Let $K$ be an infinite field and let $L:=K(\alpha, \beta)/K$ be a field extension with $\alpha$ algebraic over $K$ and $\beta$ separable over $K$. Then $L = K(z)$ for a certain $z \in L$. ...
0
votes
3answers
130 views

Fibonacci divisibility

Is $2051$ a factor of any fibonacci number? It is not a factor of any perfect number. The prime factors of $2051$ are $7$ and $293$, which are both prime. the $8$th fibonacci number, is the first ...
0
votes
2answers
16 views

Solve using Linear Congruences and Divisibility.

Let r be the common remainder when 1059, 1417 and 2312 are divided by d>1. Find the value of d-r. Find using linear congruences and divisibility.
7
votes
1answer
221 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} ...
1
vote
3answers
55 views

Number of divisors of huge numbers

How many positive integers n are there such that n is a divisor of at least one of the numbers $10^{40}$,$20^{30}$? I'm having problems with this question. I know how to find the number of integers ...
0
votes
3answers
41 views

Modular arithmetic

Hello, What is the remainder when the following sum is divided by 4? $1^5 + 2^5 + 3^5 +...+ 99^5 + 100^5$ I feel like it has to do with modular arithmetic... I am trying to decompose every number ...
2
votes
4answers
981 views

Find a 4-digit number which, divided by a 3-digit number (all unique digits) equals 9

This question is related to this Stack Overlow post. I tried following R code to find a 4 digit number divided by a 3 digit number (all unique digits) so that result equals 9: ...
0
votes
1answer
36 views

General Rule for calculating solutions to ax+by= 1 where (a,b)=1

A friend and I are in an intro to number theory class at UK and were struggling to prove the theorem that states that for two relatively prime integers $a$ and $b$ there exist integers x and y which ...
0
votes
3answers
39 views

How to prove $\gcd(a+m,b)=d$ when given $\gcd(a,b)=d$ and $b|m$?

some say I shall use $a+m-m$..... But I do not get it. Since $\operatorname{gcd}(a,b)=d$ then $a=q_1d$ and $b=q_2d$ And $b|m$ give $m= q_3b = q_3 q_2 d$ then $$a+m = q_1d+q_3q_2d = (q_1+q_3q_2)d$$ ...
2
votes
1answer
85 views

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$.

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$. This is a problem from a selection to IMO 2014.
2
votes
3answers
2k views

Rules of Division

I know a few rules number ends with even digit, it is divisible by 2 number ends with 5 or 0 is divisible by 5 if sum of all digits in a number is divisible by 3 then that number is divisible by 3 ...
0
votes
4answers
45 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
44 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
49 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 ...
2
votes
2answers
1k views

Understanding mathematical induction for divisibility

I'm on my quest to understand mathematical induction proofs (beginners). First, thanks to How to use mathematical induction with inequalities? I kinda understood better the procedure, and practiced it ...
1
vote
3answers
54 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
104 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$?
3
votes
1answer
52 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 ...
7
votes
2answers
108 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)$.
1
vote
0answers
21 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 ...
1
vote
2answers
101 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 ...
1
vote
7answers
94 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 ...
0
votes
0answers
28 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
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 ...
0
votes
0answers
32 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
52 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
25 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
44 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$?
1
vote
4answers
75 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
3answers
66 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 ...
0
votes
2answers
27 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
55 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, ...
1
vote
2answers
51 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 ...
3
votes
1answer
312 views

Choose a k-subset such that its elements 's gcd is maximal

Given $n$ positive integer and a positive integer k. How to find a subset of size k such that its elements 's gcd is maximal (just give the maximum value of gcd is okay). Example: Give $3$ integers ...
0
votes
1answer
36 views
0
votes
3answers
44 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
30 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
vote
1answer
45 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
598 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 ...
2
votes
4answers
59 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 ...
-1
votes
1answer
38 views
0
votes
0answers
10 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
16 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
38 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
2answers
31 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)$ ...
2
votes
2answers
155 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 ...