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
votes
2answers
145 views

Proof that if x is prime, then x+7 is composite. [closed]

Proof that if x is prime, then x+7 is composite. I do not know how to prove it. Can anyone help me to solve it? Thx
11
votes
2answers
261 views

Show that $A[X]/(aX+b)$ is an integral domain

Let $A$ be an integral domain, $a$ and $b \in A-\{0\}$, and let $B = A[X]/(aX+b)$. Show that, if $Aa \cap Ab=Aab$, then $B$ is an integral domain. My attempt at proof (following a hint). Denote ...
-2
votes
2answers
50 views

If $a,b,c\neq0$, prove that $ac\mid bc \iff a\mid b$ [closed]

How can I prove this question? If $a,b,c\neq0$, prove that $ac\mid bc \iff a\mid b$ Please help me
1
vote
2answers
51 views

If $n^m\mid m^n$ and $k^n\mid n^k$, prove $k^m\mid m^k$, $m,n,k\in \mathbb{Z}^+$

If $n^m\mid m^n$ and $k^n\mid n^k$, then $k^m\mid m^k$, $m,n,k\in \mathbb{Z}^+$ Aside from the definition of divisibility, can someone suggest theorems/facts that might be useful in proving this ...
0
votes
4answers
80 views

How can I show that $(x-1)(x^2-1)$ divides the polynomial $(x^n-1)(x^{n+1}-1)$? [closed]

How can I show that $(x-1)(x^2-1)$ divides the polynomial $(x^n-1)(x^{n+1}-1)$?
3
votes
2answers
72 views

$f,g,h$ are polynomials. Show that…

Let $f,g$ and $h$ be polynomials. Show that $\gcd(f,g,h)=\gcd(\gcd(f,g),h)$. I was thinking of signing $\gcd(f,g)=d$ and then write it by using Euclid's algorithm, but I couldn't get anything proper. ...
4
votes
1answer
57 views

To prove ${2p - 1 \choose p } \equiv 1 \pmod{p^2}$ without using Wolstenholme's theorem

How to prove that ${2p - 1 \choose p} \equiv 1 \pmod{p^2}$ ? I don't want to use Wolstenholme's theorem; but one might use $p|{p \choose k} , 1 \le k \le p - 1$ , and $(p - 1)! \sum_{k = 1}^{p - 1} ...
0
votes
1answer
43 views

Induction divisibility proof

Prove that $4^n \sum_{k=0}^{n} \binom nk +14n-1 $ is divisible by $7$ for every $n \geq 1$. Basic Step: For $n=1$, $21$ is divisible by $7$.($21 \mod 7 = 0$) Induction Hypothesis: Suppose that ...
2
votes
1answer
59 views

implication of a number dividing a product of relatively prime numbers

I read this recently on the web and can't manage to understand it. Not homework -- I haven't done math homework for years. If $d|ab$ and $(a,b)=1$, prove that $d=d_1 d_2$, that $d_1|a$, that $d_2|b$, ...
4
votes
3answers
114 views

Can we prove the existence of a gcd in $\mathbb Z$ without using division with remainder?

For $a,b\in\mathbb Z$ not both $0$, we say $d$ is a gcd of $a$ and $b$ if $d$ is a common divisor of $a$ and $b$ and if every common divisor of $a$ and $b$ divides $d$. With this definition, can we ...
1
vote
1answer
19 views

Use the euclidean algorithm to prove that if gcd(a,b) = 1 and a|c and b|c then ab|c

I am a bit confused here. I assume that: $gcd(a, b) = 1 \wedge c = ax_{1} \wedge c = bx_{2}$. I tried to find a formula starting from $a = bx_{3} + r$. But I didn't succeed, any tips?
0
votes
1answer
37 views

Which subrings $S$ of $\mathbb Z_n$contains a multiplicative identity , that is $\exists e\in S$ such that for every $x \in S , x.e=e.x=x$ ?

I want to find all non-trivial subrings of $\mathbb Z_n$. So let $S$ be a subring (not necessarily containing $[1]$ ). Then $(S,+)$ is a asubgroup of $(\mathbb Z_n,+)$, so $S$ is generated by an ...
1
vote
3answers
69 views

Prove $(n!-1,(n-1)!-1)=1$

Question: Let $n\geq2,n\in\mathbb{N}$. Prove $(n!-1,(n-1)!-1)=1$ I have noticed that $n!=n\cdot (n-1)!$ So letting $\alpha=(n-1)!$, we have to prove $(n\alpha-1,\alpha-1)=1$ I feel that this is ...
2
votes
1answer
34 views

Long division to primitive roots?

In this long divsion: ...
1
vote
1answer
43 views

Euclid’s Algorithm as a State Machine. Why is the set of states is N^2?

In the textbook that I am reading it is said: Euclid’s algorithm can easily be formalized as a state machine. The set of states is $N^2$ and there is one transition rule: $(x,y) --> (y, ...
11
votes
1answer
73 views

Does it follow that $(n!)^n$ divide $(n^2)!$

It is well known that $(n!)^2$ divides $(2n)!$. Does it follow that $(n!)^3$ divides $(3n)!$ and so on up to $(n!)^n$ dividing $(n^2)!$? If yes or no, could you provide the details behind the ...
1
vote
1answer
44 views

$k$ divides $\binom{kn}{n}$

For positive integers $k,n$ , is it true that $k$ divides $\binom{kn}{n}$? I can write $$\binom{kn}{n}=\frac{(kn)(kn-1)\cdots(kn-n+1)}{n(n-1)\cdots 1}$$ but must the $k$ at the top remain after ...
1
vote
3answers
91 views

Prove or disprove : if $x|y^2 $then $x|y$

How can I prove such statement? I think that if $x|y^2$ then $x|(y*y)$ so $x|y$ or $x|y$ which means that in any case $x|y$. Am I correct? I ask this question as such template because I think that ...
0
votes
0answers
31 views

Given an array, how many no. of subsequnces of array such that gcd of numbers in that subsequence will be between a and b

A sub-sequence can be obtained from the original sequence by deleting 0 or more integers from the original sequence. L <= GCD(all numbers in subsequence) <= R number of such sequences. For ...
11
votes
4answers
3k views

How many three digit numbers are not divisible by 3, 5 or 11?

How many three digit numbers are not divisible by 3, 5, or 11? How can I solve this? Should I look to the divisibility rule or should I use, for instance, $$ \frac{999-102}{3}+1 $$
0
votes
3answers
167 views

If $p$ divides $a^n$, how to prove/disprove that $p^n$ divides $a^n$? [duplicate]

The only thing I know for this problem is that an integer is a product of primes.
3
votes
4answers
70 views

Prove that $(n^2-1)\mid(n^3+1)$ iff $n=2$

Seperating $n^2-1$ into $(n+1)(n-1)$. I have noticed that $n^3+1=(n+1)(n^2-n+1)$, so we have $\forall n\geq 2$, $(n+1)\mid(n^3+1)$. We now need to show that $(n-1)\mid(n^2-n+1)$ iff $n=2$ This ...
1
vote
2answers
32 views

Is it true that GCD$(\alpha,b)=1$?

Let $d=$GCD$(a,b)$, and $\alpha,\beta\in\mathbb Z$ such that $\alpha\cdot a+\beta \cdot b=d$. Is it true that GCD$(\alpha,b)=1$?
1
vote
1answer
41 views

Prove that an r-cycle to a power k where gcd(r,k)=d>1 is a product of d disjoint cycles of length r/d.

Let $\sigma$ be an $r$-cycle and let $k \in\Bbb N$. Let $d=\gcd(r,k)$. Write $r'=r/d$ and $k'=k/d$. Prove that $\sigma^k$ is a product of $d$ disjoint cycles each of length $r'$. I think ...
1
vote
2answers
144 views

Divisibility Proof with Induction - Stuck on Induction Step

I'm working on a problem that's given me the run around for about a weekend. The statement: For all $m$ greater than or equal to $2$ and for all $n$ greater than or equal to $0$, $m - 1$ divides $m^n ...
4
votes
2answers
36 views

proof $z \mid b$ and $w\mid b$

Question I'm working on: Let $a,b$ be integers with $b$ not equal to $0$. suppose $x^2+ax+b=0$ and $x=z,w$. If $z,w$ are integers, show that $z\mid b$ and $w\mid b$. Is it sufficient for me to show ...
3
votes
1answer
59 views

Prove $\forall n\geq 2,n\in\mathbb{Z}$, $(n+1)\mid(n^3+1)$

Question: Prove $\forall n\geq 2,n\in\mathbb{Z}$, $(n+1)\mid(n^3+1)$ I know that it is possible to solve by factoring $n^3+1$ and showing that $n+1$ is a multiple, but I would like to show this via ...
1
vote
1answer
93 views

$n$ is a divider of $c$ if and only if $n = 2(c \mod (n-1)) - (c \mod(n-2)) + 2$

While working on Integer factorization problem I came to this conclusion: If and only if $n$ is a divider of $c$ $$c\mod n = 0$$ Than $$n = 2(c \mod (n-1)) - (c \mod(n-2)) + 2$$ c,n are positive ...
3
votes
9answers
261 views

Prove that for any integer, $n^2 + 5$ is not divisible by $4$.

So I got that there is two cases: odd or even. If odd then say $n^2$ is $(2k+1)^2 = 4k^2 + 4k + 1.$ then $4k^2 + 4k + 1 + 5$ would need to be divisible by 4 and I don't know where to go from there. ...
3
votes
3answers
70 views

Proving $ab(a+b)+ac(a+c)+bc(b+c)$ is even

Prove that $\forall a,b,c\in \mathbb N: ab(a+b)+ac(a+c)+bc(b+c)$ is even I tried to simplify the expression to something that would always yield an even number: $ (a+b+c)(ab+ac+bc)-3abc$ but ...
0
votes
1answer
29 views

Proving a number doesn't divide another and proving $lcm$ using the definition

Say I have two integers $a,b$ and I want to prove that $a\not \mid b$ or $ak\neq b$, do I have to take two adjacent $k$s such that $ak_1 < b$ and $ak_2> b$? Is there another way? Another ...
2
votes
4answers
53 views

Proving that if $8\mid (n^2+2n)$ then $2\mid n$

Let $n\in \mathbb N$ prove that if $8\mid (n^2+2n)$ then $2\mid n$. From the given, there exists $k\in \mathbb N$ such that $8k= (n^2+2n)$, take $k=1$, and we get $2\cdot 4 = n(n+2)$. Now my ...
9
votes
3answers
734 views

How many 0's are in the end of this expansion?

How many $0's$ are in the end of: $$1^1 \cdot 2^2 \cdot 3^3 \cdot 4^4.... 99^{99}$$ The answer is supposed to be $1100$ but I have absolutely NO clue how to get there. Any advice?
4
votes
1answer
49 views

Smallest $a$ such that both $a$ and $a+5$ and $a$ and $a+7$ have a common factor

Which is the smallest integer number $a$ so that the highest common factor of $a$ and $a+5$ is not $1$ and the highest common factor of $a$ and $a+7$ is not $1$ either? I think that it is $35$. Am I ...
4
votes
1answer
118 views

Show that $\mathrm{gcd}(x+4,x-4)$ divides $8$ for all integers $x$.

I want to prove that $\mathrm{gcd}(x-4,x+4)$ divides $8$ for all $x\in \mathbb{Z}$ Since they are both polynomials of degree $1$, it suggests that the $\mathrm{gcd}$ is a constant. Using Euclidean ...
1
vote
1answer
30 views

Prove that if $p > 3$ is a prime then $2(p-3)! \pmod{p} =-1 \pmod{p}$.

Prove that if $p > 3$ is a prime then $2(p-3)! \pmod{p} =-1 \pmod{p}$.. I am totally lost; at first I thought this could be done by induction, but unfortunately this is not possible (at least I ...
0
votes
1answer
54 views

If $a^2$ divides $b^3$, then $a$ divides $b$.

I want to prove or provide a counterexample to the following statement: $a^2|b^3 \Rightarrow a|b$. I know that $a^k|b^k \Rightarrow a|b$. My thought is that, e.g in the case of $k = 3$, where we ...
1
vote
2answers
59 views

If $X$ and $Y$ are coprime to $Z$, then so is their product $XY$

Given is $X$ is coprime to $Z$ and $Y$ is coprime to $Z$ prove $XY$ is coprime to $Z$. I know you can use Bezout's lemma to say $1=aX+bZ$ and $1=cY+dZ$ but I don't know how to actually do the proof. ...
4
votes
1answer
75 views

Prove that there are no positive integers $a, b$ and $n >1$ such that $a^n – b^n$ divides $ a^n + b^n$.

Prove that there are no positive integers $a$ , $b$ and $n>1$ such that $a^{n}–b^{n}$ divides $a^{n}+b^{n}$. Can someone provide me a proof of this and explain it to me please.
0
votes
2answers
34 views

If I have a polynomial $x^2(1-m^2) - x2m^2 - (m^2 + 1)$ with a solution at $x = -1$, how do I get the other root

If I have a polynomial $x^2(1-m^2) - x2m^2 - (m^2 + 1)$ with a solution at $x = -1$, then I know I can just take $x^2(1-m^2) - x2m^2 - (m^2 + 1)$ and divide it by $x+1$ to get the other root. In a ...
1
vote
1answer
41 views

If $p$ is a prime and $p$ divides $a^3$ then $p$ divides $a$ [closed]

I have to either give a proof or provide a counterexample for this question. $a, b$ are non-zero intergers. If $p$ is a prime and $p|a^3$ then $p|a$ I think this is true but do not know how to go ...
0
votes
1answer
45 views

Prove elements of a set are not uniquely representable.

Let $E = \{2k: k \in \Bbb{N}\}$, and let $M = \{m = (2r)(4a + 2) : r, a \in \Bbb{N}\}$. Prove that some elements in $E$ are not uniquely representable as products of elements of $M$, e.g. ...
0
votes
1answer
87 views

Solve $9x^8\equiv 8\pmod{17}$

$$9x^8\equiv 8\pmod{17}$$ Is there a way to solve this with out testing all integers $x$ between $1$ and $17$ ?
1
vote
2answers
83 views

The equation $x^4+y^4=z^2$ has no integer solution

The equation $$x^4+y^4=z^2$$ has no integer solution for $(x, y, z), x \cdot y \neq 0 , z >0$. We suppose that there is a solution $(x, y, z)$. We consider the set $$M=\{z \in \mathbb{N} | ...
0
votes
1answer
40 views

If $p^q - 1$ is a prime, then $p=2$ and $q$ is a prime [duplicate]

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : If $p$ and $q$ are positive integers ($\mathbb{Z}^+$) such that $q \gt 1$ and $(p^q - 1)$ is ...
0
votes
1answer
25 views

How to use totient function here?

I have asked this before, but I had no idea how to use Totient, now I do here is the questions: How many positive integers $< 2013$ cannot be divided by $2, 3, 5$ ?? An advice given was find ...
2
votes
1answer
52 views

For what positive integer values $b,d$ does $(b^2-d)\mid(b^2-1)?$ hold?

I am curious about the answer to the following questions: And hope that you can help me For what positive integer values $b, d$ does $$(b^2-d)|(b^2-1)?$$ hold? Is it correct that the only ...
2
votes
5answers
136 views

The divisibility of $a^p-1$ by $a-1$ and by $(a-1)^2$

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : Let a $\geq$ 2 and p be any positive integers , then prove that : $(a-1) \mid(a^p - ...
2
votes
1answer
25 views

Find $a$ and $b$ such that $g$ divides $f$ evenly

$f=2X^4-3X^2+aX+b,\ g=X^2-2X+3, \ f,g \in \mathbb{Q}[X]$ I have tried to divide $f$ by $g$ but I get $ (a+10)X +b +3$ as the remainder which looks like a bad result. I have, also, tried to factor ...
0
votes
1answer
39 views

How does the Euler Totient Function apply here?

How many positive integers $< 2013$ are divisible by $2$ Can I somehow use Euler's Totient function to find this?