Tagged Questions
4
votes
1answer
43 views
What is the largest number such that the number formed by the first $n$ digits is divisible by $n$?
What is the largest number such that the number formed by the first $n$ digits is divisible by $n$?
For example, if we have a number $$abcdefghijklm,$$ and all of these leters stand for digits,
then ...
5
votes
4answers
85 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
42 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 ...
4
votes
2answers
89 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 ...
1
vote
2answers
77 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 ...
4
votes
1answer
80 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)! $
3
votes
1answer
45 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
163 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$?
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
58 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 ...
1
vote
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
63 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
70 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
144 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.
1
vote
3answers
144 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
96 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
130 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
181 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!
5
votes
2answers
219 views
Divisibility - Math Olympiad
Show that for any positive integer $m$, there is an infinite number of pairs of integers $(x,y)$ satisfying the conditions:
i) $\gcd(x,y)=1 $;
ii) $y \mid x^2+m$;
iii) $x \mid y^2+m$.
4
votes
3answers
39 views
Problems with proof that $p|2^m-2^n$ if $p-1|m-n$
This was a homework assignment that I have already made unsuccesfully. However, no answers were given and I'm still curious. The question is as follows:
"If $p$ is an odd prime number and $m > n$ ...
4
votes
1answer
129 views
Divisibility criteria for $7,11,13,17,19$
A number is divisible by $2$ if it ends in $0,2,4,6,8$. It is divisible by $3$ if sum of ciphers is divisible by $3$. It is divisible by $5$ if it ends $0$ or $5$. These are simple criteria for ...
8
votes
3answers
188 views
Proof of Wolstenholme's theorem.?
According to the theorem :
$$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...+\frac{1}{p-1} =\frac{r}{q}$$
And we have to prove that $r= 0 \pmod{p^2}$.
(Given $ p>3$, ...
4
votes
4answers
78 views
Proving that $ \gcd(a,b) = as + bt $, i.e., $ \gcd $ is a linear combination.
For any nonzero integers $ a $ and $ b $, there exist integers $ s $ and $ t $ such that $ \gcd(a,b) = as + bt $. Moreover, $ \gcd(a,b) $ is the smallest positive integer of the form $ as + bt $.
I ...
3
votes
3answers
79 views
Prove that either $m$ divides $n$ or $n$ divides $m$ given that $\operatorname{lcm}(m,n) + \operatorname{gcd}(m,n) = m + n$?
We are given that $m$ and $n$ are positive integers such that $\operatorname{lcm}(m,n) + \operatorname{gcd}(m,n) = m + n$.
We are looking to prove that one of numbers (either $m$ or $n$) must be ...
2
votes
4answers
108 views
How can I find the possible values that $\gcd(a^3,b^4)$ can take, if $\gcd(a,b)=10$?
I don´t know how to find them, any ideas would really help.
1
vote
1answer
54 views
Function that counts the number of divisors of a natural number?
Let Function $f(n)$ be formally defined for natural numbers such that it gives number of distinct divisors of the number n (n and 1 included) For example, $f (12)=6$, then what is a quick way to ...
4
votes
2answers
132 views
Show that the difference of two consecutive cubes is never divisible by $3$.
Here is my proof:
Let $n \in \Bbb Z$. Then, $n$ is of the form $2k$(even) or $2k + 1$(odd), for some $k \in \Bbb Z$.
Without loss of generality (not sure if I can use this), let $n = 2k$.
Then, $n ...
8
votes
5answers
196 views
How can I find the possible values that $\gcd(a+b,a^2+b^2)$ can take, if $\gcd(a,b)=1$
If $\gcd(a,b)=1$, how can I find the values that $\gcd(a+b,a^2+b^2)$ can possibly take? I can´t find a way to use any of the elemental divisibility and gcd theorems to find them.
1
vote
2answers
77 views
Finding the smallest positive integer $N$ such that there are $25$ integers $x$ with $2 \leq \frac{N}{x} \leq 5$
Find the smallest positive integer $N$ such that there are exactly $25$ integers $x$ satisfying $2 \leq \frac{N}{x} \leq 5$.
1
vote
1answer
51 views
elementary divisibility argument
I am trying to argue that for distinct primes $p,q,r$ we have that
$$
\gcd (pq + qr+ pr ,pqr ) = 1 = g
$$
and I am wondering whether people find the following argument convincing :
Consider the ...
0
votes
3answers
252 views
If an integer is divisible by 8 and 15, then the integer also must be divisible by which of the following?
I'm not going to list the choices here, mainly because I just want the general idea. If I generalize the question and was given $n$ different integers divide some integer $r$, how do I determine what ...
1
vote
3answers
37 views
Proving a property of divisibility
We have to prove $b|a$ and $b|c \Rightarrow b|ka+lc$ for all $k,l \in \mathbb{Z}$.
I thought it would be enough to say that $b$ can be expressed both as $b=ka$ and $b=lc$. Now we can reason that ...
0
votes
2answers
80 views
Decimal Representaion
A rational number can be represented in the form p/q. prove that the period of the the repeating decimal should at the most q-1.
-3
votes
1answer
136 views
$S$ and $G$ are positive integers. Prove there exist integers $x$ and $y$ such that $x+y=S$ and $(x,y)=G$ if and only if $G\mid S$
So obviously because of the if and only if we must first prove that
If there exist integers $x$ and $y$ such that $x+y=S$ and $(x,y)=G$ then $G\mid S$.
And then if $G\mid S$, then there exist ...
0
votes
1answer
11 views
Values of $d$ in a congruence problem $dp \equiv s \mod N$
I'm solving an algorithm problem and it boils down to solving the congruency $$dp \equiv s \mod N$$
for the smalest value of $d$. Is there a way I can use number theory to solve this?
1
vote
2answers
49 views
Suppose $p$, $q$ are distinct odd primes, $a\in\mathbb{Z}$, and $q|a^p-1$ but $q\nmid a-1$
From the assumptions above, I am trying to prove that $q=1+kp$ for some integer $k$ and that $k$ is even.
My thoughts thus far: Since $a^p\equiv 1$ mod $q$, I know that by a corollary of Fermat's ...
1
vote
2answers
77 views
Basic theory about divisibility and modular arithmetic
I am awfully bad with number theory so if one can provide a quick solution of this, it will be very much appreciated!
Prove that if $p$ is a prime with $p \equiv 1(\mod4) $ then there is an integer ...
2
votes
2answers
50 views
Divisibility explanation needed
I thought I proved the following two divisibility statements but later I found out I was wrong. Could someone explain them?
1) For primes $q\geq 2$, $2^q-1$ is divisible by some prime $p$ such that ...
4
votes
5answers
290 views
Prove 24 divides $u^3-u$ for all odd natural numbers $u$
At our college, a professor told us to prove by a semi-formal demonstration (without complete induction):
For every odd natural: $24\mid(u^3-u)$
He said that that example was taken from a high ...
2
votes
1answer
110 views
multiple approaches/ways to prove that $1000^N - 1$ cannot be a divisor of $1978^N - 1$
Am interested in learning to do multiple proofs for the same problem, and hence I chose this problem:
Prove that for any natural number $N$,
$1000^N - 1$ cannot be a divisor of $1978^N - 1$. ...
6
votes
3answers
346 views
The positive integer solutions for $2^a+3^b=5^c$
What are the positive integer solutions to the equation
$$2^a + 3^b = 5^c$$
Of course $(1,\space 1, \space 1)$ is a solution.
6
votes
2answers
128 views
Smallest value of $(a+b)$
What can be the smallest value of $(a+b)$ , $a>0$ and $b>0$ where $(a+13b)$ is divisible by $11$ and $(a+11b)$ is divisible by $13$
This is what I have done so far.
We have
1) $a+ 13b = ...
3
votes
6answers
157 views
Show that $121^{n}-25^{n}+1900^{n}-(-4)^{n}$ is divisible by 2000.
My question comes from the British Mathematical Olympiad (Round 1) paper from 2000:
Show that $121^{n}-25^{n}+1900^{n}-(-4)^{n}$ is divisible by 2000 for any natural $n$.
My immediate idea was to ...
0
votes
0answers
23 views
Calculating a modular equation from another
If we know that the following is true for given values of $x,y,z$:
$x \equiv z \pmod y$
Then how can we then calculate the following from the previous equation:
$\frac{x}{a} \equiv ? \pmod y$
2
votes
1answer
41 views
Distribution of $\bmod$ on the $+$ operator
We know that $(a*b) \pmod n \equiv (a \pmod n * b \pmod n) \pmod n$.
What other distributive attributes of the mod exist? Specifically when we have:
$(a + b + c) \pmod n \equiv ?$
3
votes
2answers
475 views
Trying to prove that $p$ prime divides $\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$
So I'm trying to prove that for any natural number $1\leq k<p$, that $p$ prime divides:
$$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$$
Writing these choice functions in ...
