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
1answer
43 views

Divisibility !?? wihout mathematical induction if possible PLZ …

Hello I need to prove if $n\, |\, (x-a)$ and $n \, | \, f(x)$ then $n \, | \, f(a)$. It is true if $\operatorname{deg}(f)=1$ or $2$, but what for greater degree of $f(x)$? I don't know how to ...
0
votes
3answers
23 views

Divisibility involving exponents

How can one prove that $13$ divides $3^x - 16^x$ ? I have tried to apply some exponent laws but those only work when multiplying with the same base, not subtraction. Any helpful hints/advice would ...
3
votes
5answers
78 views

Show that $\gcd(a,b)>1$

Given are three natural numbers $a$, $b$ and $c$, for which $$\frac1a+\frac1b=\frac1c$$ Show that $\gcd(a,b)>1$. Could you someone provide a hint? I already tried algebraic manipulation, but I ...
-7
votes
4answers
110 views

math problem : Is (x+y+z)! is divisibleby x!*y!*z!? [on hold]

Prove that : $(x+y+z)!$ is divisibleby $x!y!z!$ Thanks
0
votes
1answer
21 views

Implications of a prime square dividing a binary quadratic form

Let $u,v$ be positive integers with $\gcd(u,v)=1$, let $k\ge 3$ be an odd integer, and fix a prime $p$. Now what are the implications of $p^2 \mid (u^2+kv^2)$? I know implications in certain cases, ...
2
votes
1answer
42 views

Is it true that if $\gcd(a,b) = 1$ and $\gcd(a,c) = 1$ then $\gcd(ac,b) = 1$?

Is it true that if $\gcd(a,b) = 1$ and $\gcd(a,c) = 1$ then $\gcd(ac,b) = 1$? I know that $\gcd(a,b) = 1$ means that there exist integers $m$ and $n$ such that $am + bn = 1$ Same thing for ...
0
votes
1answer
21 views

successive divisibility of a number by 9,8,7,6,5,4,3,2

There is a nine digit number . If you delete the digit at its unit place the remaining number would be divisible by nine, if you delete the digit at its tenth place the remaining number would be ...
-1
votes
2answers
41 views

a proof of contradiction

I am wondering whether the following is a valid proof?
-1
votes
1answer
45 views

Divisibility by 7 of a number [on hold]

if a number lies from 1 to 1000 and is an integer,then how many values of that number satisfy the following:- 4 times the number raise to the power 6 + number raised to the power 3 + 5 is a multiple ...
0
votes
1answer
36 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
2answers
13 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.
10
votes
1answer
121 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
3answers
38 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 ...
1
vote
3answers
50 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 ...
1
vote
4answers
908 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
32 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
38 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
3answers
104 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
4answers
44 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
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 ...
1
vote
3answers
53 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
96 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
53 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 ...
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
84 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
103 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
48 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
42 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
51 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
74 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
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
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
37 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
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
496 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
28 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
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
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
36 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 ...