This tag is for basic questions about divisibility.
0
votes
1answer
50 views
Probability of two random n-digit numbers dividing each other
Let $n$ be a positive integer. Suppose $a$ and $b$ are randomly (and independently) chosen two $n$-digit positive integers which consist of digits 1, 2, 3, ..., 9. (So in particular neither $a$ nor ...
0
votes
1answer
18 views
Probability of all elements of a subset being coprime
Let $S=\{1,..,n\}$ and $R \subset S$ ($|R|=k$, $k<n$) -- $R$ is a random subset of $S$. Let $m=min(R)$, and $R'=\{x-m: x \in R, x \neq m\}$, so $|R'|=k-1$.
What's the probability that ...
5
votes
1answer
27 views
Kernel of the evaluation map on a power series ring
Let $R$ be a commutative ring with unity and $r \in R$ a nilpotent element. Is it true that if $f \in R[[\epsilon]]$ satisfies $f(r) = 0$, then $(\epsilon - r) | f$ in $R[[\epsilon]]$? I tried solving ...
0
votes
2answers
66 views
Chinese reminder theorem issue
Let's say I have the following equations:
$$x \equiv 2 \mod 3$$
$$x \equiv 7 \mod 10$$
$$x \equiv 10 \mod 11$$
$$x \equiv 1 \mod 7$$
And I need to find the smallest x for which all these equations ...
1
vote
4answers
36 views
Prove divisibility using linear congruences
I need to prove that:
$$10|(53^{53} - 33^{33})$$
I can and should only use linear congruences ($a \equiv b \mod n$) - how can I do this?
4
votes
1answer
62 views
Last non zero digit of $n!$ [duplicate]
What is the last non zero digit of $100!$?
Is there a method to do the same for $n!$?
All I know is that we can find the number of zeroes at the end using a certain formula.However I guess that's of ...
0
votes
4answers
150 views
Divide by a number without dividing.
Can anyone come up with a way to divide any given x by any given y without actually dividing?
For example to add any given x to any given y without adding you would just do:
$x-(-y)$
And to ...
4
votes
4answers
78 views
Prove or disprove the following statements involving greatest common divisor
Help with prove or disproving either of these statements would be really appreciated, one or the other is fine, I just need a start or a solution to one and I'm sure I could probably figure the other ...
1
vote
2answers
41 views
Proving x and y is divisible by p (prime).
If p is a prime number and x and y are integers, how do I prove "if xy and x+y are both divisible by p, then x and y is divisible by p"?
I started like this..
1) p divides xy, so p divides x or p ...
5
votes
4answers
58 views
$20^{15} + 16^{18}$ is divided by 17
What is the reminder, when $20^{15} + 16^{18}$ is divided by 17.
I'm asking the similar question because I have little confusions in MOD.
If you use mod then please elaborate that for beginner.
...
4
votes
2answers
87 views
Find the greatest integer $k$ for which $1991^k$ divides $1990^{{1991}^{1992}}+1992^{{1991}^{1990}}$
Find the greatest integer $k$ for which $1991^k$ divides $$1990^{{1991}^{1992}}+1992^{{1991}^{1990}}$$
It is easy to see that $k \geq 1$ as $1990 \equiv -1$ and $1992 \equiv 1 \pmod{1991}$
Also, I ...
4
votes
0answers
83 views
Natural extension of the divisor function $\sigma$ to the complex integers $\mathbb{Z}[i]$
The divisor function $\sigma$ of a positive integer $n$ is defined as the sum of the positive divisors of $n$. It turns out that this definition is equivalent to
...
5
votes
3answers
109 views
Prove that $(a+1)(a+2)…(a+b)$ is divisible by $b!$ [duplicate]
The problem is following, prove that:
$$(a+1)(a+2)...(a+b)\text{ is divisible by } b!\text{ for every positive integer a,b}$$
I've tried solving this problem using mathematical induction, but I ...
1
vote
2answers
76 views
High school number theory question
When is $\dfrac{k^2-71}{7k+55}$ (where $k\in\mathbb{Z}$) a positive integer?
I can't seem to find a angle of attack for this kind of question whether I'm restricting myself to high school ...
2
votes
2answers
52 views
What is the smallest natural number divisible by the first $n$ natural numbers? [duplicate]
For example, for the numbers 1 to 10, one can just find the necessary factors and multiply them: $5 \times 7 \times 8 \times 9 = 2520$, and all the other numbers in that range follow. But with larger ...
5
votes
1answer
51 views
Does this have a name: If an odd prime $p$ does not divide $a$, then $p$ divides $a^n + 1$ or $a^n - 1$
After seeing and doing a bunch of proofs like "For all $a$ in the natural numbers, then if $7$ does not divide $a$, then $7$ divides $a^3+1$ or $a^3-1$," I conjectured the following, but got stuck in ...
4
votes
1answer
79 views
how to find all $n \in \Bbb N$ such that $n(n+1)\mid(n-1)! $
how to find all $n \in \Bbb N$ such that $n(n+1)\mid(n-1)! $
-1
votes
1answer
58 views
Proof of divisibility by 2 and 3 if and only if divisible by 6
I can't find a way of proving that:
For integer a, a is divisible by 2 and divisible by 3 if and only if a is divisible by 6.
I’m not sure where to go from here. Any help would be great!
0
votes
2answers
36 views
Division of a cubic equation by one of its factors [duplicate]
I'm trying to divide a cubic equation by a factor.
This is the equation:
$$ -\lambda^3 -\lambda^2 + 10 \lambda - 8 = 0$$
and this is the factor : $(\lambda - 1)$
I Googled about it and I found the ...
1
vote
1answer
45 views
Divisibility problem.
In line written squares of natural numbers from 1 to 2012. How many of these numbers have a remainder when divided by 17, which is divisible by 3?
2
votes
2answers
42 views
Proving that if $a,b$ are even, then $\gcd(a,b) = 2 \gcd(a/2, b/2)$ [duplicate]
Prove that if $a, b$ are both even then $\gcd(a,b) = 2\cdot\gcd(a/2,b/2)$.
Little confused here. I have tried the following but it's basically just repeating the proof unfortunately:
$a = 2 ...
1
vote
3answers
49 views
Binary Division
IF I convert the dividend and divisor into decimal, perform the division and convert the remainder and quotient back in to binary will I get correct answer?
I'm doing this:
$630 ÷ 13$
Quotient=$48= ...
3
votes
1answer
44 views
Proof involving division algorithm
I'm trying to prove the following.
Let $\text{m}$ and $\text{n}$ be positive integers, $\text{n} \gt
\text{m}$. Prove that if $\text{n}$ divided by $\text{m}$ leaves
remainder $\text{r}$, then ...
2
votes
3answers
161 views
Finding the number of odd integers $0 < n < 1000$ such that its number of divisors divides $n$
How to solve this:
For how many odd positive integers $n<1000$ does the number of positive divisors of $n$ divide $n$?
0
votes
1answer
32 views
Explanation of proof common divisor divides gcd needed
I have been given a proof that uses the gcd to show that there is no biggest prime. However (coming from a less mathematical background) I am having trouble actually understanding what it means and ...
0
votes
3answers
51 views
Reduce the size of two numbers but keep their ratio
I have two numbers: 1536 and 2048, I would like to reduce these numbers to as close as 600 as possible while retaining their ...
3
votes
3answers
81 views
can't understand a simple divisibility probelm
I am reading this book. In the example 1.1 they said to prove this problem.
probelm
Let $x$ and $y$ be integers. Prove that $2x + 3y$ is divisible
by $17$ iff $9x + 5y$ is divisible by $17$
the ...
2
votes
1answer
57 views
Prove the converse of Wilson's Theorem
... namely that if $n > 1$ and $(n − 1)!\equiv−1\pmod{n}$, then $n$ is prime.
This is for a number theory class I'm in at Penn State. My idea is to follow accordingly, but I can't get it ...
2
votes
4answers
114 views
law of divisibility on $37$
how to find and prove law of divisibility on $37$?
Thanks in advance.
Added:---- how to prove for$37$ that: Split off the last digit, multiply by 11, and subtract the product from the number that is ...
2
votes
3answers
71 views
What is the proof for: $a\mid b,a\mid c\implies a\mid b\pm c$
In my spare time, I'm working my way a book "mathematical introduction to cryptography" in which the following proposition is given:
If $a\mid b$ and $a\mid c$, then $a\mid (b+c)$ and $a\mid ...
9
votes
1answer
159 views
Elementary Number Theory; prove existence
Prove that there exists a positive integer $n$ such that
$$2^{2012}\;|\;n^n+2011.$$
I was wondering if you could prove this somehow with induction (assume that $n$ exists for $2^k|n^n+2011$ ...
1
vote
3answers
62 views
Basic Modulo Question
I've been having trouble with this example while studying for my exams. Why is
$$2023^{2297}\equiv 20 \pmod{3953}\;?$$
Thanks so much for any help I can get!
The examples solves the answer by ...
2
votes
1answer
57 views
Rectangle triangle of sides natural
Is there a rectangle triangle such that each side length is a natural number, and such that its area is a perfect square?
4
votes
6answers
97 views
Solve $91x\equiv 84\pmod{147}$
So, I posted a similar question to this, and I know that the equation is solvable because $\gcd(91,147) = 7$ and $7 \mid 84$.
Plugging into Wolfram Alpha, I found that the solution is a line $21n + ...
2
votes
2answers
69 views
Proving that if $a$ and $b$ are coprime, then $\gcd(a, c) = \gcd(ab,c)$
How to prove that if $a$ and $b$ are relatively prime, then $\gcd(a, c) = \gcd(ab,c)$?
How to make a connection between $(a,b)=1$ and $ab$? I have no idea.
8
votes
3answers
142 views
Does $a^n \mid b^n$ imply $a\mid b$?
Does $a^n \mid b^n$ imply $a\mid b$? I think it does but haven't been able to prove it.
I don't know much number theory so an elementary answer would be great.
4
votes
5answers
79 views
How to prove $x \in H$
How to prove that
Let H be a normal subgroup of a finite group G. If $\gcd(|x|, |G/H|)$ = 1,
show that $x \in H$.
2
votes
4answers
92 views
Proving $x$ is divisible by $20$
I need to prove that $x$ divisible by $20$ if and only if $x=0\pmod4$ and $x=0 \pmod 5$
proving that if $x=0 \pmod 4$ and $x=0 \pmod 5$ than $x$ divisible by $20$ is by the Chinese theorem (am I ...
1
vote
3answers
143 views
Proving that $\gcd(n!,\ n+1)=1$ or $n+1$
For any positive integer $n$ I need to prove that $\gcd(n!,\ n+1)=1$ or $n+1$ (except one integer). I need to prove both cases and for which $n$ exactly it exists.
I tried to use many gcd properties ...
2
votes
5answers
95 views
Showing that a $3^n$ digit number whose digits are all equal is divisible by $3^n$
Let $c$ be a $3^n$ digit number whose digits are all equal. Show that $3^n$ divides
$c$.
I have no idea how to solve these types of problems. Can anybody help me please?
5
votes
2answers
129 views
How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?
How to prove $\forall m,n\in\mathbb N$:
$$ 56786730 \mid mn(m^{60}-n^{60})?$$
Thanks in advance.
0
votes
5answers
179 views
Proving that if $\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;$ then $\;5\mid(a+b)$
Can you please help me a bit with this question?
How do we show that $\;$ if $\;\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;\;$ then $\;5\mid(a+b)\;$?
Thanks a lot!
2
votes
5answers
121 views
Prove that if $6 \mid (2a + 4)$ and $9 \mid (12 + 3b)$ then $3 \mid (a + b)$
Could you help me with the problem below?
Prove that if $6 \mid (2a + 4)$ and $9 \mid (12 + 3b)$ then $3 \mid (a + b)$.
Thank you!
1
vote
1answer
58 views
Smallest $x$ that allows for division by $y$
Assume we know $y$ which is prime of form $6k+1$ (may not be relevant). I want a simplified way to find the smallest positive $x$ where $y$ divides $x^2-x+1$. Is there a better way than just testing ...
3
votes
2answers
45 views
The greatest common divisor of $a$ and $b$ is a linear combination of $a$ and $b$. In general, in what kind of ring does this hold?
In $\mathbb{Z}$, the greatest common divisor of $a$ and $b$ is a linear combination of $a$ and $b$.
This generalizes to Euclidean domains since Euclid's algorithm works. Moreover this statement ...
1
vote
1answer
41 views
When an integer is disible by 17,19,23, or 41?
Let $n=a_m10^m++a_{m-1}10^{m-1}+\dots + a_{2}10^2+a_{1}10+a_0$ where $a_k$ are integers and $0\leq a_k \leq 9,k=0,1,\dots,m$ be the decimal representation of a positive integer $n$.
Let ...
0
votes
2answers
44 views
what is the rule to find the remainder for $\frac{x^y}{z}$
I am searching for any rule to find the remainder for $\frac{x^y}{z}$?
where x,y,z are positive integer.
if there is any rule to find the ans quickly then plz help me.
Thanks in advance.
3
votes
3answers
109 views
Divisibility problem: show $(x-z)\mid xy+zw \implies (x-z)\mid xw+yz$
I'm stuck at this homework problem can someone help me out? Much appreciated!
$$(x-z)\mid xy+zw \implies (x-z)\mid xw+yz$$
Thanks again!
1
vote
1answer
29 views
Pointers about the concept of 'division extensionality'?
When working a bit on another question (If $a \equiv b\pmod m$, then $\gcd(a, m) = \gcd(b, m)$), I discovered the following, which seems to be valid:
$$
a = b \;\;\equiv\;\; \langle \forall d :: d ...
1
vote
1answer
42 views
Notation for multiple of a number?
I've have a question about the notation for a multiple of a number, I know you can write it several ways: $2|4, 4 = 2n $ where $n$ is an integer, etc, but what about this one
$$4 = \dot 2$$
I've ...
