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
3answers
43 views

How to prove if $m,n\in \mathbb{Z}$,then $30\mid mn(m^4 -n^4)$

I first thought I'd just have to do cases, i.e. if $m,n$ are even, $m=2l, n=2k$, where $k, l\in \Bbb Z$. But even in this case, alone, I wind up with $4kl(16l - 16k) = 64k(l^2) - 64l(k^2)\dots$ and ...
0
votes
5answers
63 views

How to prove that $7^{15} + 7^{16} + 7^{17} - 1$ is divisible by $10$?

This was a question on my math exam. We weren't able to use calculators so proving by manually calculating the exact value would take too long. In the end I ignored this question to save time but I'm ...
2
votes
4answers
327 views

Proof that $3^c + 7^c - 2$ by induction

I'm trying to prove the for every $c \in \mathbb{N}$, $3^c + 7^c - 2$ is a multiple of $8$. $\mathbb{N} = \{1,2,3,\ldots\}$ Base case: $c = 1$ $(3^1 + 7^1 - 2) = 8$ Base case is true. Now assume ...
1
vote
2answers
89 views

Is 7^2015 + 4^2015 divisible by 17? Explain your reasoning and show your work.

Is $7^{2015} + 4^{2015}$ divisible by 17? Explain your reasoning and show your work. I'm confused on how exactly I would do this. Would I need to use Fermats Theorem?
1
vote
0answers
36 views

Looking applications for these statements involving multiplicative functions and Euler-Fermat theorem

It is well knwon that for positive integers such that $gcd(a,n)=1$, Euler-Fermat Theorem states than $a^{\phi(n)}\equiv 1 \mod n$, where $\phi(n)$ is the Euler totient function counting positive ...
1
vote
1answer
57 views

How to prove: if $a$ is an even integer, $\gcd(a^3 - 1, a + 1) = 1$

I have very little idea of how to tackle this question. I know if $a$ is even, $a = 2L$, for some $L$ in the integer set.
3
votes
4answers
87 views

Prove that $5\mid 8^n - 3^n$ for $n \ge 1$ [duplicate]

I have that $$5\mid 8^n - 3^n$$ The first thing I tried is vía Induction: It is true for $n = 1$, then I have to probe that it's true for $n = n+1$ $$5 \mid 8(8^n -3^n)$$ $$5 \mid 8^{n+1} -8\cdot3^...
2
votes
1answer
91 views

Expected number of digits of the smallest prime factor of $1270000^{16384}+1$

The number $N\ :=\ 1270000^{16384}+1$ with $100,005$ digits is given. Given, that $N$ is composite and does not have a prime factor below $2\times 10^{13}$, what is the expected number of digits ...
0
votes
3answers
49 views

Let N be a four digit number, and N' be N with its digits reversed. Prove that N-N' is divisble by 9. Prove that N+N' is divisble by 11.

Let $N$ be a four digit number, and $N'$ be $N$ with its digits reversed. Prove that $N-N'$ is divisible by $9$. Prove that $N+N'$ is divisible by $11$. I let $N=abcd$ and $N'=dcba$ but I dont see ...
-1
votes
2answers
80 views

Prove that if a|b, c|d, then ac|bd [duplicate]

I'm trying to prove it, but I can't find how. If a divides b, and c divides d, then ...
0
votes
5answers
112 views

Prove: If $n^2$ is odd, then $n$ is odd. [duplicate]

$n$ is a natural number. I want to prove that, if the square of $n$ is odd, then $n$ itself is odd. Any hints welcome and preferred. Thank you!
-1
votes
2answers
50 views

Show that if $a, b$, and $c$ are integers with $(a,b)=(a,c)=1$, then $(a,bc)=1$ [duplicate]

Show that if $a, b$, and $c$ are integers with $(a,b)=(a,c)=1$, then $(a,bc)=1$ I don't know exactly that I should use the division algorithm or $(a,b)=d$, $(a/d,b/d)=1$. This is my first time to ...
6
votes
1answer
67 views

$\frac{2n\choose n}{n+2}\not\in\mathbb N$ and $n\neq3k+1$ and $n\neq4k+2$

Are there any natural numbers $n\not\equiv1\bmod3$, and $n\not\equiv2\bmod4$, so that $~\dfrac{\displaystyle{2n\choose n}}{n+2}\not\in\mathbb N$ ? Since $C_n=\dfrac{\displaystyle{2n\choose n}}{n+1}\...
1
vote
1answer
36 views

Divisibility test using perhaps binomial thorem

I have to determine if $17^{21} + 19^{21}$ is divisible by any of the following numbers (a) 36 (b) 19 (c) 17 (d) 21. I am trying to find using binomial expansion but getting stuck up with one or two ...
2
votes
2answers
215 views

Order of group element divides order of finite group

Proving this can be done as follows: consider a finite group G and elements $g_i \in G$ for some integer $i$. Now consider $\langle g_i \rangle = \{g_i^n: n\geq 0\}$, a generator. It can be proved ...
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 ...
3
votes
0answers
18 views

Knapsack - Saving Waste

I am trying to figure out the most efficent way to save waste. I've looked into the knapsack problem as I believe it is what can help me solve this dilemma. Any help, guidence, or direction is ...
1
vote
3answers
114 views

divisibility question: if two integers can both divide each other, do they have to be equal? [duplicate]

if x ,y ∈ Z. and x|y,y|x,then x does NOT equal to y. Can anyone give me a counter example please?
2
votes
1answer
51 views

Number Theory Prime Reciprocals never an integer

I'm in number theory and I currently have these problems assigned as homework. I've looked through the sections containing these problems and I've solved/proved most of the other problems, but I can't ...
4
votes
2answers
57 views

Prove that $2^n+(-1)^{n+1}$ is divisible by 3.

Prove that $2^n+(-1)^{n+1}$ is divisible by 3 for $n\in\mathbb{N}$. My attempt: For $n=1$: $2^1+(-1)^2 = 2 + 1 = 3, 3 |3$ We assume that $3|(2^n+(-1)^{n+1})$ Then for $n+1$: $2^{n+1} + (-1)^{n+2}...
2
votes
2answers
123 views

Prove these two elements are not associated in $\mathbb Q[x,y,z]/(x-xyz)$ [duplicate]

So the full problem was: Consider $R=\mathbb Q[x,y,z]/(x-xyz)$. Prove that $x$ and $xy$ divide each other in $R$ but that they are not associates. In other words, there is no unit $u\in R$ so ...
3
votes
1answer
53 views

Number Theory Positive Divisor Problems

I'm in number theory and I've been assigned these problems for homework. I've searched throughout the relevant section of the book but I can't seem to find anything that relates to solving these ...
5
votes
1answer
82 views

Maximum amount of divisors of the number $n^m+m^n$

We are given some positive integer $m$. What maximum amount of distinct prime divisors a number $n^m+m^n$ can have, where $n\in\mathbb{Z}_+$? Edit: As noted in comments, there is no reason to think ...
2
votes
2answers
48 views

Showing that a number is not divisible by another.

I am currently in a number theory class, but we don't have a textbook and even though I have been attending all the lectures we have not solved a problem similar to this in class. We have never proved ...
0
votes
1answer
22 views

How can I improve my basic proof about divisibility

Hello I am wondering if my approach is on the right track or not. I want to show that if $m \in \mathbb{Z}$ and $m \neq 0$ is a solution to the equation $x^2+ax+b=0$ where $a, b$ also are integers ...
2
votes
2answers
102 views

Number Theory: Prove there are infinitely many primes $p$ satisfying $n\mid (p-1)$

I've been assigned the following problem for my homework: For any $n\in N$ show there are infinitely many primes $p$ satisfying $n\mid (p-1)$. I think I've proved it, but I'm uncertain since we were ...
0
votes
0answers
13 views

Is division by $\sum x_i-\bar{x}$ actually null?

I'm trying to find out what are $\hat{β_1}, \hat{β_2}$ $ \left \{ \begin{array}{c @{=} c} \frac{∂S( \hat{β_1}, \hat{β_2})}{∂S \hat{β_1}} =-2\sum(yi − \hat{β_1} − \hat{β_2}xi) = 0, \\ \frac{∂S(...
2
votes
0answers
52 views

How can I construct a number $n$, such that $gcd(n+k,100!)\ne 1$ for all $k=0,…,256$

Here : https://oeis.org/search?q=2%2C4%2C6%2C10%2C14%2C22%2C26%2C34%2C40%2C46&sort=&language=german&go=Suche it is indirectly claimed that there exists a number $n$, such that $n+k$ has ...
3
votes
4answers
464 views

If $a | b$, prove that $\gcd(a,b)$=$|a|$.

If $a | b$, prove that $\gcd(a,b)$=$|a|$. I tried to work backwards. If $\gcd(a,b)=|a|$, then I need to find integers $x$ and $y$ such that $|a|=xa+yb$. So if I set $x=1$ and $y=0$ (if $|a|=a$) or ...
1
vote
2answers
198 views

What are the “units” and “non-trivial divisors of zero” in a ring?

I'm confused on what units and non-trivial divisors of zero are when it comes to rings. For example, say I have this finite ring: R=GF(2)[x] mod x^3 + 1 = 0. Now I know the elements are 0, 1, x, x + ...
-1
votes
1answer
25 views

Why does this condition check the expectation?

Let's suppose n as an Integer. Let's suppose i as an Integer. To check whether the given i ...
2
votes
3answers
130 views

How to prove that $4^n-3n-1$ is divisible by 9?

How can I prove that $4^n-3n-1$ is divisible by $9$? I tried dividing the expression by $9$ and seeing if the terms cancelled in any predictable way but I still cannot prove it. Maybe there is a ...
0
votes
1answer
17 views

Formula that devides date(given in millisecounds)

Just to clarify at the offset, i am a javascript developer and this is a Math question , so my question is as follows: suppose i create to dates in javascript like so: var d1 = new Date(2005,12,4);...
6
votes
2answers
43 views

If $(b,n)=1$, $n\mid(ad-bc)$ and $n\mid(a-b)$ then $n\mid (c-d)$.

Pretty straightforward. I am stuck on a problem, and would love it if someone could give me a small hint or nudge in the right direction. The problem is $(b,n)=1$ and $n\mid(ad-bc)$ and $n\mid(a-b)$ ...
1
vote
3answers
34 views

Polynomial Divisibilty Test

I recently came across a question in a book and I was wondering how to go about solving this. I just need a hint about how I could approach it. I have to show that $x^{6n+2} - x^{6n+1} + 1$ is ...
0
votes
0answers
19 views

Why can we not let variable $p$ equal the number such that when multiplied by zero equals one.

Suppose we have a variable p such that when multiplied by zero equals one. In such case suppose when we do $1/0 = p$. This would satisfy the case $(1/0) \cdot 0 = 1$ again. Why do we not have a ...
6
votes
1answer
67 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 ...
4
votes
1answer
48 views

Do we conclude from these relations that $ny-hx \mid x(nx-h)$?

We have the following relations $$p^i \mid ny-hx \\ (ny-hx)q=(nx-h)n^f \\ p^i \mid x(nx-h)$$ where $p$ is a prime, $x, y \in \mathbb{Z}$, $n>1$, $|h|<n$, $hx\geq 0$, $i>0$. Do we conclude ...
2
votes
3answers
67 views

If $\gcd(a,b)=1$ , then $a-b$ does not divide $a+b$?

I think the following statement is true: Suppose $a,b\in \mathbb{N}^+$, such that $\gcd(a,b)=1$ and $|a-b|\geq\mathbf3$. Then $a-b$ does not divide $a+b$. Can you help me to solve this problem?
1
vote
1answer
55 views

If $p\equiv 3\pmod{4}$ and $p\mid x^2+y^2$, prove $p\mid x,y$.

I have to prove that if $p$ is a prime number of the form $p = 4n - 1$, $n\in N$ and $x^2+y^2\equiv 0\pmod{p}$, then $x\equiv 0\pmod{p}$ and $y\equiv 0\pmod{p}$. I have gone about this as follows and ...
1
vote
4answers
40 views

Quick question about divisibility

If $ a| x^2 $ does that mean that $a$ will also always divide $x$? Also if $x^2$ has a remainder $b$ when divided by $a$ could you prove that $x$ also has a remainder b when divided by $a$ ?
1
vote
1answer
82 views

When is the difference between two triangular numbers a prime number?

When is the difference between two triangular numbers a prime number? and what is the rule? I have tried drawing it out,graphs and tables however I have been unsuccessful in finding an answer. Source:...
1
vote
3answers
85 views

check if large number $(9^{81}+6)$ is divisible by $11$

I would like to know if there is a mathematical way to check whether number $9^{81}+6$ is divisible by $11$, without actually calculating the whole number.
2
votes
3answers
62 views

Proof that $3\mid n^3 − 4n$

Prove that $n^3 − 4n$ is divisible by $3$ for every positive integer $n$. I am not sure how to start this problem. Any help would be appreciated
1
vote
3answers
60 views

Show that $n-m$ is a multiple of 9 when $n$ and $m$ have same digits

I have just proved the divisibility rule for 3 and 9. Let $n\in\mathbb{N}$. Let $m$ be a number that appears when you shuffle the digits in $n$. Show that $n-m$ is a multiple of 9. Can anyone offer ...
1
vote
1answer
58 views

Proving Euclid's lemma

The lemma is shown in several ways. This is what I am exposed to (the simplest case I assume): Let $p, a, b \in \mathbb{N}$ with $p > 1$. Then p is a prime $\iff p|ab \implies p|a \lor p|b$ I ...
3
votes
1answer
80 views

For what values $m \in \mathbb{N}$, $\phi(m) | m$, where $\phi(m)$ is the Euler function.

I am working with elementary number theory and, although in theory the $\phi$ Euler function seems easy to understood, I am having some problemas making the exercises. For example, in this question: ...
0
votes
3answers
101 views

Do odd numbers have only odd divisors?

Is it true, that odd numbers have only odd divisors? If yes, what would a formal proof look like?
0
votes
3answers
69 views

For numbers divisible by three, why is the sum of their digits able to be divided by three? [duplicate]

When you add the digits of any number that is divisible by three, that sum of those digits also appears to be divisible by three (with no remainder). For example a number (which I randomly grab from ...
1
vote
1answer
40 views

Prove that $\begin{pmatrix} 2n \\ n \end{pmatrix}$ is not divisible by $p$

Let $n$ be an integer greater than $5$. I would like to prove that if $p$ is a prime such that $\displaystyle \frac{2}{3}n < p \leq n$ then $\displaystyle \begin{pmatrix} 2n \\ n \end{pmatrix}$ is ...