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
2answers
63 views

Divisibility of $2^n-n^2$ by 7

How many positive integers $n<10^4$ are there such that $2^n - n^2$ is divisible by 7?
2
votes
2answers
21 views

Prove $\gcd(a,c)=\gcd(a,b)=1$ if $c \mid (a+b)$ and $\gcd(a,b)=1$

If $a,b,c\in\mathbb{Z}$, $\gcd(a,b)=1$ and $c \mid (a+b)$ then prove $$\gcd(a,c)=\gcd(b,c)=1$$ I think this can be proven with linear combinations but I'm not sure how to go about starting the ...
0
votes
4answers
35 views

Dividing factorials

I'm told that $\dfrac{(n+1)!}{(n+2)!}$ simplifies to $\dfrac{1}{n+2}$, but I dont understand how this works. Could someone explain the theory of how to divide factorials like this?
4
votes
2answers
51 views

Proof by contrapositive: $ 4 \nmid (n-2)^2 \implies 6 \nmid n $

Prove: $ 4 \nmid (n-2)^2 \implies 6 \nmid n $ Proof by contrapositive: $ 6 \mid n \implies 4 \mid (n-2)^2 $ $n=6k,$ $ k \in \mathbb Z $ $((6k)-2)^2 = 36k^2 - 24k+4 = 4(9k^2 - 6k+1), (n-2)^2=4c$ ...
0
votes
4answers
42 views

Let $n$ be an integer. Prove that if $2|(n^2-1)$ then $4|(n^2-1)$.

Let $n$ be an integer. Prove that if $2|(n^2-1)$ then $4|(n^2-1)$. I know that $n^2=2k$ for some integer $k$. Please help me continue.
0
votes
1answer
13 views

n where it gives certain remainder for certain number

I am studying for GRE and need help with following question When the positive integer n is divided by 3, the remainder is 2 and when n is divided by 5, the remainder is 1. What is the least ...
0
votes
2answers
57 views

Prove $\forall a,b \in \mathbb{Z}, 18a + 6b \ne 1$

Prove $\forall a,b \in \mathbb{Z}, 18a + 6b \ne 1$ Is there a way to do this using proof by contradiction without using mod?
0
votes
1answer
34 views

Techniques of division by numbers in base n

Our current number system is in base 10, so we have devised techniques when a number is divided by a power of 10. For example: $\dfrac{350}{100} = 3.5$, by moving the decimal by two places because 100 ...
3
votes
2answers
39 views

Does $R=\{(x,y) \in \mathbb{Z}\times\mathbb{Z} : 3|(x+y)\}$ define an equivalence relation?

Given $R=\{(x,y) \in \mathbb{Z}\times\mathbb{Z} : 3|(x+y)\}$, Is $R$ reflexive? Is $R$ symmetric? Is $R$ transitive? Reflexivity: Could $(1,1)$ be a counter-example because $3\nmid(1+1)$? Symmetry: ...
2
votes
2answers
104 views

Define a relation on the integers such that $a R b$ iff $\;3\mid (a + 2b)$?

I've seen relations defined as functions between sets and as sets of ordered sets; however, I've never seen a relation defined as $3\mid(a+2b)$. What does this mean? --Edit-- I'll try and express my ...
0
votes
1answer
21 views

Question with Divisibility proof

I have a simple proof question: Suppose $a,b \in \Bbb Z$ where $a|b$. If $a|(b-c)$, then $a|c$. I have solved it below, but is my way a valid answer? Is there a better clear way of proving this? ...
3
votes
3answers
19k views

Numbers till 400 divisible by 2, 3, 5, 7

I stumbled upon the following in a book: till 400 all even numbers will be divisible by 2 ( 200 even numbers) remaining 200 odd numbers 1 3 5 7 9 ..... 399 200/3 = 67 will be divisible by 3, ...
3
votes
0answers
100 views

Lehmer's totient problem generalization (adding a constant )

Lehmer's totient problem is an well-known open problem which states that the divisibility : $$\phi(n) \mid n-1$$ holds only for primes . This motivated me to ask the following : For which ...
-2
votes
1answer
30 views

Zero-infinity hypothesis [duplicate]

math.stackexchange community. I have joined to inquire on a hypothesis a friend of mine has recently proposed. Please note: before posting this, I have repetitively told him that his logic is flawed ...
0
votes
4answers
59 views

Prove that for all integers $a$ and $b$ that $a + b$ and $a − b$ are either both odd or both even.

Prove that for all integers $a$ and $b$ that $a + b$ and $a − b$ are either both odd or both even. Stumped on this proof. I've only been able to figure it out assuming that both a and b are even: ...
0
votes
2answers
62 views

Direct proof that the product of odd integers is odd

Prove $P(x,y)$: If $x$ and $y$ are odd integers, then the product $xy$ must also be odd. I need a direct proof of this. I know that $ x $ and $y$ both have to equal to $2n+1$ in order for them ...
1
vote
7answers
91 views

$n^2 + 7n + 1$ is odd

Prove that for any integer $n$, the integer $n^2 + 7n + 1$ is odd. I have $n=2k+1$ for some $k\in Z$ I really do not how to do this problem. any help in understanding would be greatly appreciated.
1
vote
1answer
56 views

If $r$ is a nonzero solution $ x^2 + ax + b$, prove that $r | b$

I know that if $r$ is a solution, then there exist two factors of $b$ that when multiplied equal $b$ and that $r$ is one of them. So clearly $r$ divides $b$, but I don't know if there is any other way ...
5
votes
2answers
47 views

Deleting one digit yields a divisor

Let $N$ be a positive integer with $d\geq 4$ digits, none of which is zero. Suppose that erasing some digit of $N$ yields another number $M$ which happens to be a divisor of $N$. Examples : 1375 ...
6
votes
2answers
29 views

Number Theory: Reordering $c_1,\dotsc,c_{10}$ so that $(2k-1)\mid(a_k-b_k)$

I have this homework problem that I'm confused on how to do: Given any distinct $z_1,\dotsc,z_{10}\in\mathbb{Z}$, show that one can reorder these as $s_5,s_4,\dots,s_1,t_5,\dotsc,t_1$ so that ...
2
votes
1answer
201 views

How do I divide Laurent polynomials?

I have an example from a paper (listed below) that I cannot figure out. I can divide normal polynomials, but the alternative ways to divide Laurent polynomials is beyond me at the moment. The paper ...
2
votes
0answers
51 views

Can Someone approve the formula for the number of groups of order $p^2q$

Here https://www2.bc.edu/~reederma/Groups.pdf on page $112$, a table of the number of groups of order $p^2q$ is given. In the explanations, there is a typo ($\frac{q+5}{5}$ instead of ...
7
votes
5answers
661 views

Math induction problem with large numbers

I am trying to figure out how to prove $17^{200} - 1$ is a multiple of $10$. I am talking simple algebra stuff once everything is set in place. I have to use mathematical induction. I figure I need ...
1
vote
1answer
56 views

How can we show the other direction?

I want to prove the following implication: $$k \in \mathbb{Z} \Leftrightarrow ce^x-1 \mid c^ke^{kx}-1$$ For the direction $\Rightarrow$ I tried the following: $k >0$: $$\sum_{i=0}^{k-1} ...
3
votes
2answers
34 views

Number Theory: Show that $10^{3^n}\equiv 1\pmod{3^{n+2}}$ but $3^{n+3}\not\mid 10^{3^n}-1$

Show that for all $n\in\mathbb{N}$, $10^{3^n}\equiv 1\pmod{3^{n+2}}$ but $3^{n+3}\not\mid 10^{3^n}-1$. I think I've proved this problem, but I was unsure if my proof was correct: Proof Let $n=1$. ...
5
votes
3answers
321 views

Why would some elementary number theory notes exclude 0|0?

I am studying elementary number theory, and just started learning about divisors. I always, try to read several other sources mostly because it helps me understand ideas better, also the textbook I ...
3
votes
2answers
2k views

What is the probability that 5 digit number divisible by 6?

The main constraint is that each digit can only take digits from $\{1, 2, 3, 4, 5\}$. So the sample space will be $5^{5}$. What is the probability that a random number taken from this sample space ...
3
votes
1answer
153 views

Problem from Olympiad from book Arthur Engel

Each of the numbers $a_1 ,a_2,\dots,a_n$ is $1$ or $−1$, and we have $$S=a_1a_2a_3a_4+a_2a_3a_4a_5 +\dots+ a_na_1a_2a_3=0$$ Prove that $4 \mid n$. If we replace any $a_i$ by $−a_i$ , then $S$ ...
0
votes
1answer
12 views

Sow divisibility with congruence equation

I have this math question that I'm kind of stuck on. Suppose that the congruence equation $ax \equiv b \pmod{n}$ has at least one solution. Let $d = \gcd{(a, n)}$. Show that $d \mid b$. I ...
3
votes
1answer
41 views

Show, that for every k$\in \mathbb N$ , $2^n+3^n-1,2^n+3^n-2,…,2^n+3^n-k$ are all composite for some $n$

Show that for every $k\in \mathbb N$ there exists a number $n\in\mathbb N$ ,such that $2^n+3^n-1,2^n+3^n-2,...,2^n+3^n-k$ are all composite.
1
vote
5answers
202 views

How to prove that $42|a^7-a$? [duplicate]

Suppose we are given a number $a \in \mathbb{Z}$ prove that $42|a^7-a$. I'm not too sure how to start any ideas?
2
votes
2answers
44 views

If three distinct integers are chosen at random, show that there will exist two among them, say $a$ and $b$, such that $30 | (a^3b-ab^3)$

Problem: If three distinct integers are chosen at random, show that there will exist two among them, say $a$ and $b$, such that $30 | (a^3b-ab^3)$ My work: $a^3b-ab^3=ab(a+b) (a-b)$ and if $30 ...
1
vote
3answers
211 views

Show by induction : $n^7-n$ is a multiple of 7

I have to prove this : "$n^7-n$ is a multiple of 7". This is what I have done this so far : $P(n):n^7-n$ On putting $n=1,$ $P(1):1^7-1=0$, which is a multiple of 7. So, $P(1)$ is true. Let $P(k)$ be ...
3
votes
3answers
6k views

Prove: The product of any three consecutive integers is divisible by $6$. [duplicate]

I'm new to number theory and was wondering if someone could help me with this proof. Prove: The product of any three consecutive integers is divisible by $6$. So far I have ...
-2
votes
3answers
68 views
1
vote
1answer
44 views

Proof that 6 divides $a \in \mathbb{Z}, a(a^2 - 7)$

I am trying to prove a question from my tutorial sheet, is this an acceptable proof? Six cases exist: $$a,k \in \mathbb{Z}, a(a^2 - 7) = 6k \\\text{Proof:}\\ a = 0 \mod 6 \longrightarrow a^2 = 0 \mod ...
2
votes
2answers
493 views

Use congruences to show that $6$ divides $n^3 – n$ for every integer $n$

Use congruences to show that $6$ divides $n^3 – n$ for every integer $n$. I did this same problem using induction, and I don't understand how to do it using congruences. Is this using modulo?
3
votes
3answers
88 views

For all integers $n \ge 1$, prove 6 divides $n(n+1)(n+2)$ by PMI.

For all integers $n \ge 1$, prove 6 divides $n(n+1)(n+2)$ by PMI. I check for my base case, it holds. Then, my inductive hypothesis that for any arbitrary $n \ge 1$, 6 divides $n(n+1)(n+2)$ so ...
6
votes
7answers
817 views

Prove $3|n(n+1)(n+2)$ by induction

I tried proving inductively but I didn't really go anywhere. So I tried: Let $3|n(n+1)(n+2)$. Then $3|n^3 + 3n^2 + 2n \Longrightarrow 3|(n(n(n+3)) + 2)$ But then?
5
votes
1answer
65 views

Can $2^{1947}\times 5+1|2^{2^{1945}}+1$ be shown by hand?

A long tima ago, I read in a book that it would be easy to show that the number $2^{1947}\times 5+1$ divides the Fermat number $2^{2^{1945}}+1$ I do not know, if the author meant, that it can be ...
1
vote
1answer
42 views

Use Fermat's Little Theorem to show [duplicate]

Show, with the help of Fermat’s little theorem, that if $n$ is a positive integer, then $42$ divides $n^{7} − n$. I don't really know how to show Fermat is about primes. I have a slightly idea about ...
0
votes
2answers
110 views

The multiplication of two even numbers gives an even number

I am given the following proposition: If $m$ and $n$ are even integers, then $mn$ is also an even integer. This is my strategy: An integer $m$ is said to be even if it is divisible by 2 (integer). ...
1
vote
3answers
82 views

If $a $ divides $b$, then $(2^a-1) $ divides $(2^b-1)$ [duplicate]

Prove that if $a \mid b$, then $(2^a-1) \mid(2^b-1)$. So, I've said the following: Let $a \mid b$. $ \implies b=am$ Assume $(2^a-1) \mid (2^b-1)$ $ \implies (2^b-1)=(2^a-1)x$ But I can't ...
5
votes
2answers
2k views

Is zero a multiple of any number?

nooby question. I heard many times that 0 is a pair number. I'm fairly sure that the definition of pair is multiple of 2. Yet I heard too that multiples of a prime number p are only 1 and p, ...
2
votes
2answers
74 views

Proving ${\rm gcd}(a,b)=1$, $a\mid c$ and $b\mid c$ implies $ab\mid c$ WITHOUT Euclid's or Bezout's lemma.

I want to show prove the following statement: For any $a,b,c\in\mathbb Z$, if $a,b$ are coprime and both $a$ and $b$ divide $c$, then $ab$ has to divide $c$ as well. Before marking this as a ...
6
votes
4answers
104 views

Divisibility of polynomials in a subfield of a field.

I am trying to prove the following assertion: Let $K\subset L$ be fields, let $f,g\in K[x]$ be such that $f\mid g $ in $L[x]$, then $f\mid g$ in $K[x]$. We clearly have that $fh=g$ for some ...
2
votes
5answers
81 views

A counterexample to “$k\mid n$ if and only if $k\mid n^2$”

I am looking to prove the following statement false: Let $k$ be a positive integer, then $k\mid n$ if and only if $k\mid n^2$. So I am trying to find a $k$ where this does not hold but after ...
2
votes
3answers
80 views

If the cube of $n$ is divisible by $3$, then $n$ is divisible by $3$

Trying to figure the statement $3|n$ iff $3|n^3$. While proving the forward direction was easy and stuck on the reverse direction. Any ideas?
0
votes
1answer
27 views

Polynomial $p$ divides polynomial $q$ infinitely often.

Let $p(n)$ and $q(n)$ by polynomials with integer coefficients such that $p(n)|q(n)$ for infinitely many integers $n$. Is there a polynomial $r(n)$ such that $q(n)=p(n)r(n)$? Note that this is not ...
2
votes
9answers
824 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. ...