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
vote
3answers
106 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
50 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
52 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} + ...
2
votes
2answers
120 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
50 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
81 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
99 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
12 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, \\ ...
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
461 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$) ...
1
vote
2answers
184 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
102 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 ...
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
65 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
53 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
59 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. ...
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
59 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
59 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
79 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
91 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
59 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 ...
0
votes
1answer
25 views

Isolating Decimals

I'm in need of isolating the decimal part of a number using maths only, no excel functions or anything like that, but it's proving to be much harder than I thought it would be. For example, I have ...
19
votes
3answers
2k views

Prove that there exists a number divisible by 1999 with digit sum 1999

My nephew in the secondary school asked me how to solve the problem as stated in the title. Honestly, I do not have any idea how to do it: Prove that there exists a positive integer number such ...
1
vote
3answers
18 views

Remainders and modulars

How do I find the remainder of $3^{2002}$ divided by $5$ using mod? I can solve the remainder of, for example, $7^{220}$ divided by $8$ because $7=-1 \pmod 8$, but that doesn't work here.
3
votes
1answer
87 views

The value of $\gcd(2^n-1, 2^m+1)$ for $m < n$

I've seen this fact stated (or alluded to) in various places, but never proved: Let $n$ be a positive integer, let $m \in \{1,2,...,n-1\}$. Then $$\gcd(2^n-1, 2^m+1) = \begin{cases} 1 ...
1
vote
1answer
40 views

Showing existence in proof of Division Algorithm using induction

Division Algorithm: Let $a$, $b$ $\in \mathbb{Z}$ be any integers and $b \neq 0$. Then, $\exists$ unique integers $q$, $r$ such that $a = bq + r$ and $0 \leq r < |b|$. I am trying to show ...
1
vote
1answer
84 views

Show that there exist infinitely many $i$ such that $a_i-1$ is divisible by $2^{2015}$

Let $(a_n)$ be a sequence defined by: $a_o=2, a_1=4, a_2=11$ and $\forall n \geq 3$, $$a_n = (n+6)a_{n-1}-3(2n+1)a_{n-2}+9(n-2)a_{n-3}$$ Show that there exist infinitely many $i$ such that $a_i-1$ is ...
0
votes
3answers
61 views

Euclid's proof on the infinity of primes

Could someone shed some light on this? I perfectly understand Euclid's proof on the infinity of primes. Let's suppose there is a largest prime, p, and then let's make a number, n, so that n = (2 x 3 ...
0
votes
2answers
49 views

$n>k>0$ are integers , then among the integers $n , n+1 , …, n+k-1$ , there is an integer containing a prime divisor greater than $k$ ? [closed]

If $n>k>0$ are integers , then how to show that among the integers $n , n+1 , ..., n+k-1$ , there is an integer containing a prime divisor greater than $k$ ?
2
votes
1answer
46 views

$2(n-2)+1$ does not divide $(n-2)(n-3)/2$ for $n \ge 8$

For $n \ge 8$ the number $2(n-2)+1$ never divides $(n-2)(n-3)/2$. Any ideas how to prove this? I see that $(n-2)(n-3)/2 = 1 + 2 + \ldots + (n-3)$. If I suppose that $2(n-2)+1$ divides ...
0
votes
4answers
110 views

Is it correct that $\frac{1}{0}=\frac{1}{-0}$ and if it is, why is $\frac{1}{0} \neq 0$?

This is a genuine question, I am not trying to convince anyone. But I'm sure hundreds of people already considered this, so if you can point out where I'm wrong, it would be much appreciated. If we ...
1
vote
2answers
48 views

Proof for elementary divisibility problem

Not sure if my thinking is correct. For the problem "$a$ divides $b$ if and only if $a$ divides $b^2$." So far my proof goes: since $a$ divides $b$ there exists an integer $n$ such that $b=an$. Then ...
1
vote
7answers
94 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.
3
votes
0answers
38 views

Prove that $2\mid x$ and $5\mid x$ if and only if $10\mid x$

I have to do it without using Fundamental Theorem of Arithmetic. Can someone check my work? Prove if $2\mid x$ and $5\mid x$, then $10\mid x$. Let $x \in \mathbb{Z}$. Suppose $2\mid x$ and $5\mid ...
3
votes
0answers
87 views

$1+2^x+\ldots+n^x \mid 1+2^y+\ldots+n^y$ for all $n$ implies $x=y$?

The following problem was proposed by A. Schinzel a couple of days ago at the 22nd Conference on Number Theory, held in Liptovsky Jan (Slovakia). He pointed out that the question has an affirmative ...
4
votes
0answers
62 views

Systems of linear modular equations with unknowns in the moduli

I am interested in systems of linear modular equations, where the unknowns also appear in the moduli. The general form would be: $A \vec{x}= \vec{b} \;\textrm{mod} \; (C \vec{x}+\vec{d})$ where A ...
0
votes
4answers
43 views

Show that 2|n(n+1) using induction [duplicate]

Show that 2|n(n+1) using induction I tried but im stuck , it still (n+1)(n+2) Two successive numbers It's simple using the the methode that n=2k or n=2k+1 Can someone help or give a hint ?
2
votes
1answer
81 views

Is it possible for $(900q^2+ap^2)/(3q^2+b^2p^2)$ to be an integer?

The original problem is: "Find all possible pairs of positive integers $(a, b)$ $$k = \dfrac{a^3+300^2}{a^2b^2+300}\tag1$$ such that $k$ is an integer." I've tried so many different ways. Now this ...