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

learn more… | top users | synonyms

0
votes
2answers
57 views

Writing a GCD of three numbers as a linear combination

i know how to find the $\gcd(5,11,2^{2015}-1)$. but i can't seem to find the linear combination. do you find it the same way we find the linear combination of two integers.
1
vote
1answer
14 views

quadratic form polynomial divisibility vs. matrix pointwise multiplication.

Given matrix $V',W',Y'$ is of $d\times m (d\le m)$ ; column vector $c$ is of size $m$; $r_i, i=1,...,d$ are distinct; and each row of the matrix A is $A_i=(r_i^0 ... r_i^{d-1})$. So, A is of $d\times ...
3
votes
1answer
64 views

Find all $c\in\mathbb Z^+$ for which $\exists a,b\in\mathbb Z^+, a\neq b$ with $a+c\mid ab$ and $b+c\mid ab$

Find all $c\in\mathbb Z^+$ for which $\exists a,b\in\mathbb Z^+, a\neq b$ with $\begin{cases}a+c\mid ab\\b+c\mid ab\end{cases}$ For those $c$, prove only finitely many $(a,b)$ exist. ...
0
votes
2answers
84 views

Find the probability that an integer selected between 1 and 5000 is divisible by at least one of 3, 5 and 7

I'm having a hard time finding the solution. I can find integers that are divisible by only one of them, but there are many that are divisible by two of them. That's the problem. Find the probability ...
4
votes
5answers
110 views

Proof that $(n^7-n^3)(n^5+n^3)+n^{21}-n^{13}$ is a multiple of $3$.

I proved that $$(n^7-n^3)(n^5+n^3)+n^{21}-n^{13}$$ is a multiple of $3$ through the use of Little Fermat's theorem but i want to know if there exist other proofs(maybe for induction). How can I ...
1
vote
1answer
38 views

Analytical solution for $\max{x_1}$ in $(x_n)_{n\in\mathbb{N}}$

Let be $x_1,x_2,x_3,\ldots,$ a sequence of positive integers. Suposse the folowing conditions are true for all $n\in\mathbb{N}$ $n|x_n$ $|x_n-x_{n+1}|\leq 4$ Find the maximun value of $x_1$ I ...
1
vote
4answers
65 views

How find the fractional part of $5^{200}$ divided by $8$?

Finding the fractional part of $\frac{5^{200}}{8}$. I've had this problem given to me (we're learning the Binomial Theorem and all.) So obviously I thought I'd apply the binomial theorem to it, ...
1
vote
2answers
95 views

Contest Problem - Divisibility

Find all ordered pairs (x, y) of positive integers x, y such that $x+y$ divides 2014 and (simultaneously) $x^yy^x$ divides $(x+y)^{(x+y)}$ . This is a contest problem from U Tenn, FERMAT contest. My ...
6
votes
11answers
229 views

Prove that $n^2(n^2+1)(n^2-1)$ is a multiple of $5$ for any integer $n$. [closed]

Prove that $n^2(n^2+1)(n^2-1)$ is a multiple of $5$ for any integer $n$. I was thinking of using induction, but wasn't really sure how to do it.
5
votes
8answers
222 views

Why is $n^2+4$ never divisible by $3$? [duplicate]

Can somebody please explain why $n^2+4$ is never divisible by $3$? I know there is an example with $n^2+1$, however a $4$ can be broken down to $3+1$, and factor out a three, which would be divisible ...
4
votes
1answer
33 views

Proving divisibility of $\sum\limits_{r=1}^{p-1} {r^{p^n}}$ by p.

Let $p>2$ be an odd number and let $n$ be a positive integer. Prove that $p$ divides $${\sum\limits_{r=1}^{p-1}{r^{p^n}}}$$ My Proof: From multinomial expansion, we know that $${(1 + 2 + 3 + ... + ...
2
votes
2answers
54 views

Properties of Greatest Common Divisors

I really want to have help verify these properties of GCD: Let $s,t \in \mathbb{Z}$ and $m,n$ be positive integers with $m\mid n$. If $\gcd(t,n)\mid\gcd(s,n)$, then $\gcd(t,m)\mid\gcd(s,m)$. If ...
0
votes
2answers
48 views

divisibility of complex numbers

I want to show that $(a + bi)|(c + di)$ is equivalent to the statement that the ordinary integers $(a^2 + b^2)|(ac + bd)$ and $(a^2 + b^2)|(-ad + bc)$. I also want to show that $(a + bi)|(c + di) ...
4
votes
1answer
26 views

Square Roots: Variables with Exponents.

Alright, so let me get this straight: $\sqrt{x^2} = |x|$ $\sqrt{x^3} = x\sqrt{x}$ $\sqrt{x^4} = x^2$ $\sqrt{x^6} = |x^3|$ Are these correct?
0
votes
4answers
41 views

Question on modulus

Is $x|y$ the same as $x \equiv 0\! \mod\!{y}$ ? If not then how should it be written?
1
vote
2answers
24 views

Find the largest size of squares that can pave a given rectangle

The floor of a hall 252cm long, 162cm wide is paved with equal squares. Find the largest size of marble and number required, if only whole marbles are used. See the attempted solution posted as ...
1
vote
0answers
17 views

$x\in\mathcal{O}_K$ can be written as product of irreducible elements

Lemma: Every element $x\neq 0$ of $\mathcal{O}_K$ with ($K$ an arbitrary number field) can be written as a product of irreducible elements. Proof: We prove this lemma by complete induction on ...
4
votes
1answer
114 views

Is there a fast divisibility check for a fixed divisor?

Is there a fast algorithm to check if $d \mid n$ is true for varying $n$, if divisor $d$ is fixed? Variable $n$ is a $w$-bit binary integer, $d$ is an integer constant.
10
votes
4answers
171 views

Divisibility of $6^{2^n}+ 8^{2^n} +12^{2^n}+14^{2^n}+16^{2^n}+18^{2^n} +24^{2^n} +28^{2^n}+42^{2^n}$

Prove or disprove that for all natural $n$ $$6^{2^n}+ 8^{2^n} +12^{2^n}+14^{2^n}+16^{2^n}+18^{2^n} +24^{2^n} +28^{2^n}+42^{2^n}$$ is divisible by $259$. I tried to apply mathematical induction, but ...
1
vote
4answers
64 views

Is $\gcd(2^{2n}+1, 3)=1$?

Can any one prove that $2^{2n}+1$ and $3$ are relatively prime for any integer $n$? I tried with a Matlab program and computed this gcd upto $n= 25$. I got 1 for all of them. So I suppose that the ...
1
vote
2answers
44 views

If $n \in \mathbb N$, under what conditions are $n$ and $n+2$ relatively prime?

The Statement of the Problem: If $n \in \mathbb N$, under what conditions are $n$ and $n+2$ relatively prime? My Thoughts: I know that the answer is that $n$ must be odd. However, I'm not sure how ...
1
vote
2answers
61 views

Interesting $0, 1$ sequence of numbers,after $n>2, a_n$is composite.

Let us have a finite sequence with only $0$ and $1$ digit in our numbers(it can begin with $0$ too). $a_n$ is the number, which we get if we write our number $n$ times next to each other. Prove, that ...
4
votes
3answers
66 views

Prove that ${x^2+y^2=z^n}$ has a solution in $\mathbb{N}$ for all $n$ in $\mathbb{N}$

I am solving it by stating that $$x^2 +y^2 =c^2$$ represents a circle. And when $$c^2=z^n$$ then , it represents a system of concentric circles with radius varying as $z$ varies or $n$ varies. So, for ...
4
votes
1answer
41 views

Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \le j \le n$

Let $p$ be a prime number and $a_1, a_2, \ldots, a_n$ be integers. Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \leq j \leq n$. The hint was to use induction. ...
1
vote
2answers
45 views

GCD theory - gcd(x, y) = 1

Take $n + 1$ numbers out of $1, 2, ..., 2n$. Show that there will be two numbers $x, y$ so that $gcd(x, y) = 1$. What I've got is: Let $d=gcd(a,b)$; by definition there are integers $a′$ and $b′$ ...
2
votes
2answers
47 views

Suppose $p$ is a prime number and $a$ is an integer. Show that if $p \mid a^n$, then $p^n \mid a^n$ for any $n \geq 1$?

I know that if $p \mid a^n$, I can say $a^n = pr$ for some integer $r$, you can also conclude that $\gcd(p, a^n) = p$, but I'm not sure how to use that information if I even can to show that $p^n \mid ...
2
votes
1answer
26 views

Prove that if $a, b, n\in \mathbb{N}, n\geq2\longrightarrow \sqrt[\leftroot{-2}\uproot{2}n]{a}\in \mathbb{Q} \iff a=b^n$.

Prove that if $a, b, n\in \mathbb{N}, n\geq2\longrightarrow \sqrt[\leftroot{-2}\uproot{2}n]{a}\in \mathbb{Q} \iff a=b^n$. I'm at a complete loss here, I tried using the order of a prime function but ...
2
votes
1answer
37 views

Example of a domain where all irreducibles are primes and that is not a GCD domain

One has the following relations for a domain $R$: $R$ GCD domain $\Rightarrow$ All irreducible elements are prime $R$ PID $\Rightarrow$ $(R$ GCD domain $\land$ $R$ statisfies ACCP$)$ $R$ UFD ...
1
vote
1answer
88 views

Fermat's Little Theorem and prime divisors

Let $a,b\in\Bbb N$ and $a+b$ be an even number. Assume $a^2 - b^2 - a$ is an exact square, say $c^2$. Let $m = \frac {a+b}2$ and $n = \frac {a-b}2$. Then, $$(4m-1)(4n-1) = 4(4mn-m-n) + 1 = ...
2
votes
1answer
46 views

An expression with gcd and abs is transformed magically!

There's a problem to calculate $\sum^{n}_{i=1}\sum^{m}_{j=1}\frac{|i-j|}{\gcd(i,j)}$, whose tutorial gives the following transformation I really don't understand. ...
6
votes
2answers
111 views

Pythagorean Triples : Is every positive integer $\gt$ $2$ part of at least one Pythagorean triple?

I was doing some basic number theory problems from Rosen and came across this problem: Show that every positive integer $\gt$ $2$ is part of at least one ...
5
votes
1answer
131 views

Pythagorean Triples : Show that exactly one of $x$, $y$, and $z$ is divisible by $5$

I was doing some basic number theory problems from Rosen and came across this problem: Show that if $(x, y,z)$ is a primitive Pythagorean triple, then exactly one of $x$, $y$, and $z$ is divisible ...
0
votes
5answers
104 views

Mathematical induction [duplicate]

Prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ where $n$ is a nonnegative integer. I have seen many questions on this site that contain the answer to this problem and I already know the solution, ...
2
votes
1answer
52 views

Proving $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 [duplicate]

I am trying to prove that $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 for all $k \in Z$. I am not even sure what tags to use because I am not sure of right methods to ...
3
votes
1answer
37 views

Decide if there exist $a$ and $b \in \mathbb{Z}$ such that $a^2=2b^2$.

Decide if there exist $a$ and $b \in \mathbb{Z}$ such that $a^2=2b^2$. $a,b \neq 0$ We have to solve this kinds of problems using the order of a prime function: $v_p(a) \in \mathbb{Z}$ which tells ...
2
votes
3answers
75 views

$5 \nmid 2^{n}-1$ when $n$ is odd

I want to prove that $$5 \nmid 2^{n}-1$$ where $n$ is odd. I used Fermat's little theorem, which says $2^4 \equiv 1 \pmod 5$, because $n$ is odd then $4 \nmid n$ , so it is done. can you check it ...
6
votes
2answers
131 views

Prove or disprove : $a^3\mid b^2 \Rightarrow a\mid b$

I think it's true, because I can't see counterexamples. Here's a proof that I am not sure of: Let $p_1,p_2,\ldots, p_n$ be the prime factors of $a$ or $b$ \begin{eqnarray} a&=& ...
0
votes
3answers
46 views

Find $GCD(n^2+1,n+1)$

$GCD(n^2+1,n+1)$, $n\in \mathbb{N}$ What I did: $n^2+1=(n-1)(n+1) + 0$ So I thought $(n^2+1:n+1)=n+1$ But that doesn't seem to be the case: $n=2$ $n^2+1=5$ $n+1=3$ $GCD(5,3)=1$ Why is the ...
1
vote
2answers
20 views

Prove the order of the group homomorphism of an element divides the order of the element.

Let $\phi : G \rightarrow H$ be a group homomorphism. Prove $\forall g \in G$, the order of $\phi(g)$ divides $g$. I've gotten to the point where I've shown that if, $ord(\phi(g)) < ord(g)$ then ...
1
vote
2answers
55 views

For a primitive Pythagorean triple $(a, b, c)$, is it always true that $\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1$?

Let $(a, b, c)$ be a primitive Pythagorean triple. I know that $\gcd(a,b,c) = 1$. Is it always true that $\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1$?
0
votes
3answers
29 views

Binary remainder not equal to the decimal remainder

I am having a weird result. I am dividing the binary number $10101010100000$ by $10011$. In binary division. I get $R= 0100$ which is 4. However, If I consider the decimal representation of the ...
3
votes
3answers
59 views

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? [duplicate]

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? $${p^mn \choose p^m} = \frac{(p^mn)!}{p^m!(p^mn-p^m)!} = ...
1
vote
2answers
184 views

how $1/0.5$ is equal to $2$?

My question is how $1/0.5$ is equal to $2$. I am not asking the mathematical justification that $1/0.5=10/5=2$. I know all this. I just want to know how it is two... a lay man justification. ...
2
votes
1answer
56 views

How to show that $\mathbb Z+x \mathbb Q[x]$ is a GCD domain?

How to show that $\mathbb Z+x \mathbb Q[x]$ is a Bezout domain, that is, the sum of two principal ideals is again a principal ideal ? Or at least, how to show that it is a GCD domain ? (This will then ...
4
votes
3answers
84 views

Looking for an example of a GCD domain which is not a UFD

I know that every UFD (unique factorization domain) is a GCD domain i.e. g.c.d. of any two elements, not both zero, exists in the domain. I am looking for an example of a GCD domain which is not ...
3
votes
1answer
77 views

Polynomials and Divisibility Rule.

The question is this - If $f(x)$ and $g(x)$ are two polynomials such that the polynomial $h(x)=xf(x^3)+x^2g(x^6)$ is divisible by $x^2+x+1$, then which of the following are true? 1. $f(1)=g(1)$ ...
1
vote
1answer
31 views

Finding a natural number $k>1$ such that $k$ divides $(26+35n)$ and $(3+7n)$

I am trying to find a natural number $k>1$ such that $k$ divides $(26+35n)$ and $k$ divides $(3+7n)$ for some integer $n$. I know that $(ka)=(26+35n)$ for some $a \in Z$ and $(kb)=(3+7n)$ for some ...
2
votes
4answers
87 views

Prove that if $3|mn$, then $3|m$ or $3|n$

I am trying to prove this for integers $m$ and $n$. I tried to reach prove that $3|m$ by assuming that 3 does not divide $n$, but this is such a basic assumption of mine already that it is hard for ...
0
votes
1answer
45 views

If $m\mid n$ then $p^m-1\mid p^n-1$ [duplicate]

I know $m$ ,$n$ are two positive integer numbers such that $m\mid n$. If $p$ is a prime number, I want to show $p^m-1\mid p^n-1$.
0
votes
3answers
34 views

How to formally prove: if $d\mid da+b$, then $d\mid b$?

How would I formally prove that for the integers $a$, $b$, and $d$, if $d\mid da+b$, then $d\mid b$? Would a direct proof be the best option? If I do a direct proof I seem to get stuck pretty ...