This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

learn more… | top users | synonyms

2
votes
1answer
105 views

Prove that it is NOT true that for every integer $n$, 60 divides $n$ if and only if 6 divides $n$ and 10 divides $n$.

This is Velleman's exercise 3.4.26 (b): Prove that it is NOT true that for every integer $n$, 60 divides $n$ iff 6 divides $n$ and 10 divides $n$. I do understand that a number will be ...
10
votes
2answers
192 views

Can the identity $ab=\gcd(a,b)\text{lcm}(a,b)$ be recovered from this category?

Define the category $\mathcal{C}$ as follows. The objects are defined as $\text{Obj}(\mathcal{C})=\mathbb{Z}^+$, and a lone morphism $a\to b$ exists if and only if $a\mid b$. Otherwise $\text{Hom}(a,b)...
3
votes
2answers
76 views

If $2xy$ divides $x^2+y^2-x$, prove that $x$ is a perfect square [duplicate]

This problem is from ( BMO Exam1991 ). I tried to solve but it was difficult. The problem is: If $ x^{2} + y^{2} - x $ is a multiple of $ 2xy $ where $x$ & $y$ are integers, prove that $x $ ...
3
votes
0answers
38 views

Is there a name for the least exponent $e$ such that a power of an integer is divisible by another?

Say the primes dividing $m$ also divide $n$. Is there a name for the least exponent $e$ such that $m | n^e$? I can write that explicitly using the prime factorizations of $m$ and $n$, but am ...
1
vote
1answer
15 views

$\gcd(ca,cb)\mid ca$ and $\gcd(ca,cb)\mid cb \to \gcd(ca,cb)\mid cd$.

Let $(ca)x + (cb)y = cd$ where $d = (a, b).$ Then since $\gcd(ca,cb)\mid ca$ and $\gcd(ca,cb)\mid cb \to \gcd(ca,cb)\mid cd$. I don't get how they deduced the conclusion. For one thing, $\gcd(...
6
votes
2answers
109 views

$\gcd (ca, cb) = \gcd (a, b)c$ if $c > 0$ [duplicate]

Let $\gcd (a, b) = d$. So, $ax + by = d$ for some $x, y$. Then $(ca)x + (cb)y = cd$. Thus, $\gcd (ca, cb) = cd = \gcd(a, b)c$. Does it work?
4
votes
3answers
315 views

Find all integers such that $2 < x < 2014$ and $2015|(x^2-x)$

Find all integers, $x$, such that $2 < x < 2014$ and $2015|(x^2-x)$. I factored it and now I know that $x > 45$ and I have found one solution so far: $(156)(155)= (2015)(12)$. It's just that ...
3
votes
2answers
70 views

Is there a Divisibility Metric for Numbers?

Both prime numbers and highly divisible numbers have a common characteristic: divisibility. The former are divisible by as few lower numbers as possible, and the latter by as many as possible, like ...
3
votes
2answers
64 views

If $p$ and $q$ are primes, which binomial coefficients $\binom{pq}{n}$ are divisible by $pq$?

If $p$ and $q$ are primes, which binomial coefficients $\binom{pq}{n}$, $1 \le n < pq$, are divisible by $pq$? In particular, if $p$ and $q$ are distinct odd primes, and $n$ is even, does $pq \...
1
vote
1answer
41 views

Permutations where no partial sum is divisible by 3 (contest question)

A permutation of the integers $1901,1902\dots 2000$ is a sequence in which each of those integers appears exactly once. Given such a permutation, we form the sequence of partial sums $$s_1 = a_1,\...
1
vote
1answer
64 views

Divisibility proofs for greatest common divisor

I am studying divisibility and greatest common divisors. I have reached a section where I need to prove properties. My question is: are my proofs substantial? Or do I need to add to them? Below are ...
0
votes
1answer
31 views

Is this assertion about g.c.d. true? [closed]

Is it true that if $\gcd(a,bc)=1$ and $\gcd(b,c)=1$ then $\gcd(a,b^2)=\gcd(a,c^2)=\gcd(ab^2,c^2)=\gcd(a,(bc)^2)=1$? Many thanks.
5
votes
1answer
125 views

Prove that $(ab,cd)=(a,c)(b,d)\left(\frac{a}{(a,c)},\frac{d}{(b,d)}\right)\left(\frac{c}{(a,c)},\frac{b}{(b,d)}\right)$

I'm working through Oystein Ore's Number Theory and its History. On p. 109, I'm stuck on #2. The question asks the reader to verify the following identity [Note: $(x,y)=\gcd(x,y)$]: $$(ab,cd)...
16
votes
2answers
358 views

Prove that neither $A$ nor $B$ is divisible by $5$

Let the sum $$ {1+ \frac12 + \frac13 + \frac 14+ \dots +\frac1{99} + \frac 1{100}}$$ be written as $\frac AB$, where $A$ and $B$ are positive integers with no common factors. Show that neither $A$ ...
0
votes
0answers
20 views

What is the multiplicative order of 1+sqrt(2) in Z[sqrt(2)]? [duplicate]

I want to know that 1+sqrt(2) in Z[sqrt(2)], I am not sure what is multiplicative order.please guide also multiplicative order also. Actually I am in context of Contemporary Algebra by Joseph A ...
-2
votes
2answers
170 views

What is the multiplicative order of $1+\sqrt{2}$? [closed]

Actually I am in the context of Contemporary Algebra by Gallian, where there is topic of divisibility in integral domains, where there is inverse of $1+\sqrt{2}$ in $\mathbb Z[\sqrt{2}]$. I understand ...
0
votes
1answer
82 views

divisibility relations in sets.

How to draw an arrow diagram, a digraph and the matrix representation for the specified relation? The "divides" relation $|$ from the set $\{0,1,2\}$ to the set $\{0,3,6,9\}$
-1
votes
4answers
243 views

How can I find The Multiplicative Inverse of $1+\sqrt{2}$? [closed]

I am doing contemporary abstract algebra and am working in an integral domain. I have found it necessary to compute the multiplicative inverse of $1+\sqrt{2}$; I know such the definition of a ...
3
votes
5answers
846 views

Prove $\gcd(n, n + 1) = 1$ for any $n$

Let $n \in \mathbb Z$ be even. Then $n + 1$ is odd. So, $2$ doesn't divide $n + 1$. Thus there's no even number for which $\gcd(n, n+1)$ is not $1$. I am not sure how to show it for odd numbers. Is ...
2
votes
1answer
55 views

complex long division

For example we have $(2+7i)(4-i)=15+26i$. What I am after is some kind of long division method so that: $(2+7i)|\overline{15+26i}=x+yi$ If we guess $x=4$ we get a remainder of $7-2i$, but is there (...
4
votes
4answers
257 views

Prove that $2730$ divides $n^{13} - n$ for all integers $n$. [duplicate]

Prove that $2730$ divides $n^{13} - n$ for all integers $n$. What I attempted is breaking $2730$ into $2, 3, 5$, and $7, 13$. Thus if I prove each prime factor divides by $n^{13} - n$ for all ...
2
votes
1answer
43 views

I have plugged $p/q$ into the equation. Not sure what to do next.

Suppose $a_0,a_1,\dots,a_n$are integers and $a_0\neq 0$ and $a_n\neq 0$.Consider the polynomial $f(x)=a_0x^n+a_1x^{n-1}+\dots+a_{n-1}x+a_n$. If $p\neq 0,q>0$ are coprime integers and $p/q$ ...
-1
votes
3answers
79 views

Using induction to prove that $2 \mid (n^2 − n)$ for $n\geq 1$

Use induction to prove that, for all $n \in \mathbb{Z}^+$, $2\mid (n^2 − n)$. That is, I am supposed to use induction to prove that $(n^2 − n)$ can be divided by $2$ when $n$ is a positive integer. ...
0
votes
1answer
53 views

If $c = \gcd(a, b)$ then $c^2\mid ab$

I was given this question below in class today but I'm unsure on how to do it and where to start. We learnt about this in class today but it was with numbers rather than letters so it has thrown me ...
-2
votes
3answers
107 views

Division problems

I came across these problems : 1) Find the lowest natural number $k$ that satisfies the condition : $ 7 \mid A$ , where $A = 194^{19} + 125^{14} + k $ 2) Find the different prime numbers ...
12
votes
2answers
493 views

Show divisibility by 7

I was stuck at this question: Suppose $a^2+b^2=c^2$ for $a,b,c \in \mathbb Z$, and neither $a$ nor $b$ is a multiple of 7. Show that $a^2-b^2$ is a multiple of 7 I tried to write $b^2$ as $c^2-a^...
1
vote
2answers
217 views

Probability of getting a five digit number divisible by 5 but with no two consecutive digits identical

A five digit number is written down at random. What is the probability of getting a number that is both divisible by 5 and doesn't have any 2 consecutive digits identical? I tried to analyse the ...
12
votes
0answers
266 views

Dividing the whole into a minimal amount of parts to equally distribute it between different groups.

Suppose we have a finite amount of numbers $x_1, x_2, ..., x_n$ ($x_i\in\mathbb{N}$) and an object that should be divided into parts in such a way that it can be without further dividing distributed ...
5
votes
3answers
198 views

Is $a=\frac{1992!-1}{3449\times 8627}$ a prime number?

Is $a=\dfrac{1992!-1}{3449\times 8627}$ a prime number ? This is a natural follow-up to that recent MSE question We know that $a$ has $5702$ digits and no prime divisor $<10^6$.
1
vote
2answers
40 views

Explain 'expressing a number using its digits'

While studying divisibilty and prime numbers in my maths book (IB Mathematic Higher Level Option 10: Discrete Mathematics), I came across an explanation of a way to '[express] a number using its ...
-3
votes
1answer
50 views

How would you divide a polynomial by another polynomial whose power is greater than its nominator? [closed]

I have a polynomial which is: $$\frac{(x^3-4x)}{(4x^2-4x+1)} = -10$$ Is there a way to do this? I have thought about doing long division which was not helpful...
3
votes
1answer
147 views

Prove that $n \in \mathbb{Z}^\star \Leftrightarrow n \mid 1$ and $n-1 \mid 1$ or $n+1 \mid 1$, and $(x-1)/(t-1) \equiv n \pmod {t-1}$

I want to prove the following lemma: Let $F[t,t^{-1}]$ be the ring of the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$ and assume that the characteristic of $F$ is zero. ...
1
vote
1answer
55 views

Least Common Multiple and Greatest Common Divisor

Prove that if $\mathop{\mathrm{lcm}}( a, b) + \gcd(a, b) = a+b$, $a$ divides $b$ or $b$ divides $a$. This problem seemed simple at first, however I cannot figure out a way to prove this. If I assume ...
0
votes
3answers
51 views

proof for divisibility

Prove without the use of congruences that $341$ divides $2^{340} - 1$. This was a question I found in a book right after which Fermat's little theorem is discussed. I tried using it for the proof but ...
0
votes
0answers
21 views

Divisibility in $\mathbb C[t]$

I am looking for all the polynomials $P,Q,R\in\mathbb C[t]$ such that $121P^2+614PQ+841Q^2-R^2$ divides $11P+29Q-R$. I remarked that $$121P^2+614PQ+841Q^2=(11P+29Q)^2-24PQ.$$ So, $$121P^2+614PQ+841Q^2-...
2
votes
1answer
190 views

Why is the sum of any ten consecutive Fibonacci numbers always divisible by $11$?

I was wondering if anyone has any insights regarding the fact that the sum of any $a_1, \dots, a_{10}$ consecutive Fibonacci numbers is divisible by $11$ (and furthermore equals to $a_7*11$). What can ...
1
vote
0answers
39 views

Is this :$\sum_{n=1}^{\infty} \frac{\sigma_{k}(n)}{n!} $ irrational series for every natural number $k$?

Is this: $$\sum_{n=1}^{\infty} \frac{\sigma_{k}(n)}{n!} $$ irrational series for every natural number $k$? Where : $\sigma_{k}(n)=\sigma(\sigma(\sigma(\dots n)))$ is the $k$-th iterate of the sum of ...
1
vote
2answers
33 views

$k | x^{k} - x,$ for $k, x \in \mathbb{Z}$?

I seem to have found that: $$k | x^{k} - x, \ \text{for} \ k, x \in \mathbb{Z}.$$ I have tried it with a few values, and it seems to be true. I am sure that this has been discovered before.
3
votes
4answers
65 views

How do I show that we can't write $N=114^n-1$ as sum of $3$ squares for all natural number $n>2$?

I run some computations in wolfram alpha, I see that we can't write :$$N=114^n-1$$ as sum of $3$ squares, then Hop someone who can show me how I do prove that we can't write $N=114^n-1$ as sum of $3$ ...
0
votes
0answers
47 views

Divisibility Question [duplicate]

If $(ab+1)$ divides $(a^2+b^2)$ then prove that $(a^2+b^2)$ when divided by $(ab+1)$ gives a square of an integer.
4
votes
5answers
136 views

Show that $4$ does not divide $x^3-2$

Show that $4$ does not divide $x^3-2$ is what I need to prove. I think I should put $4k$ is $x^3-2$ and then contradict it somehow. Alternatively is to factor it out as $x^3$ is $x(x+2)(x-2)$ but I ...
2
votes
2answers
122 views

Prove that rational numbers $a,b$ are integers if $a+b$ and $ab$ are integers

I have been trying to prove this via divisibility, assuming that $a=\frac{n}{m}$ and $b=\frac{r}{q}$ for some $n,m,r,q$ in Ints($m$,$q$ not $0$), but I'm completely stuck here. Any help?
0
votes
1answer
41 views

How do I show that :$\sigma({p^m})$ is divisible by $4$ if $m=4k+1$ , and $k$ is an integer number?

How do i show this if it's not an open problem :$\sigma({p^m})$ is divisible by $4$ if $m=4k+1$ , and $k$ is an integer number and p is prime number. and $\sigma({p^m})$ is sum divisors of $p^m$ ...
2
votes
2answers
82 views

When does :$\sigma(\sigma(2n))=\sigma(\sigma(n))$ and $\sigma(n)$ is sum divisors of the positive integer $n$?

Is there someone who can show me When does: $$\sigma(\sigma(2n))=\sigma(\sigma(n))$$ where : $\sigma(n)$ denote the sum divisors of the positive integer $n$ ? Note (1) : I accrossed this problem when ...
35
votes
3answers
794 views

Prove that there exist infinitely many integers $(n^{2015}+1)\mid n!$

I conjecture that there exist infinitely many integers $n$ such that $$(n^{2015}+1)\mid n!.$$ I have seen a simpler problem that there exist infinitely many integers $n$ such that $(n^2+1)\mid n!$....
0
votes
1answer
84 views

Prove: If $d|a$ and $d|b$ then $d^2|ab$

Prove: If $d|a$ and $d|b$ then $d^2|ab$ All I have $ab = kd^2$, $k$ some integer. I'm stuck and hoping someone could walk me through this!
-6
votes
1answer
52 views

Proof - a | b and b | a then a = b [closed]

For all integers a and b, if a | b and b | a, a = b. Can something think of a proof? I have done this: Proof: Suppose m and n are integers such that m|n and n|m, but n ≠ m. Let m = 1 and n = -1 ...
0
votes
2answers
60 views

How do I show $1$ is not a trivial odd perfect number?

This question related to my this question in MO ,some comments stated that the integer $1$ is trivial answer for this question ,but here i'm very confused when we say that the sum divisors of $1$ is $...
3
votes
1answer
98 views

Numbers divisible by all of their digits: Why don't 4's show up in 6- or 7- digit numbers?

For reasons I'll explain below the question if you're interested, I stumbled across a peculiar phenomenon involving numbers divisible by their digits. I'm concerned with numbers that are divisible by ...
0
votes
1answer
33 views

Determine overall ratio from individual ratios

I have a set of statistics that I need to find the overall ratio to. This example will work with only two items so I'll write them down: ...