Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

2
votes
4answers
77 views

Prove $\sum_{i=2}^{n}\frac{1}{(n-1)n}$ = $\frac{(n-1)}{n}$ using induction.

I need to prove $\sum_{i=2}^{n}\frac{1}{(i-1)i}$ = $\frac{(n-1)}{n}$ using induction. I am getting stuck midway through the inductive step. Here is what I have: $\forall n\geq 2$, where ...
6
votes
2answers
92 views

Prove that $\forall n > 1 \quad2^n - 1 \pmod n \neq 0$

Prove that $\forall n > 1, \quad2^n - 1 \pmod n \neq 0$ I've thought of the induction but I can't figure out how to prove the step. Fermat's theorem (and its variations) aren't particularly useful ...
0
votes
1answer
18 views

Computing Large Number Modulo and Multiplicative Inverse

Prove that $3^{28}$ is a multiplicative inverse of $9^{34}$ modulo $17$, i.e. show that $3^{28}9^{34}\equiv 1\pmod {17}$. I really have no idea how to approach this example other than applying ...
0
votes
3answers
31 views

Postage stamp with $6$ and $7$ cents question

What is the largest postage in cents that cannot be paid exactly with an unlimited supply of $6$-cent and $7$-cent stamps? Any hint so that I can proceed?
22
votes
2answers
1k views

What is the millionth decimal digit of the $ 10^{10^{10^{10}}} $-th prime?

What is the millionth decimal digit of the $10^{10^{10^{10}}}$th prime? (This prime, with more than $10^{10^{10}}$ decimal digits, is far larger than the largest "known" prime.) The answer should ...
1
vote
1answer
17 views

Maya Lists the Positive Divisors

Maya lists all the positive divisors of $2010^2$. She then randomly selects two distinct divisors from this list. Let $p$ be the probability that exactly one of the selected divisors is a perfect ...
2
votes
16answers
3k views

How to Prove the divisibility rule for $3$

The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large ...
1
vote
3answers
36 views

$\gcd(1000, 1000 - x)$ if $0 < x < 1000$, $x \in \mathbb{N}$.

Find $\gcd(1000, 1000 - x)$ if $0 < x < 1000$, $x \in \mathbb{N}$ and $x$ is coprime to $1000$. Since $1000 > 1000 -x$, it follows from Euclidean Algorithm, $$1000 = 1(1000 - x) + x$$ ...
1
vote
3answers
24 views

How to prove that $n$ is a prime number iff for every integer $a$: $(a,n)=1$ or $n\mid a$

It seems like it's obvious because if $n$ is prime then its gcd with every number is $1$... But I understand that by intuition and don't know how to formally prove it... I'm confused.
2
votes
1answer
50 views

Number of pairs $(A,B)$ with $\gcd(A,B)=B, A \ne B^2$ with $A,B \le n$

How many pairs $(A,B)$ of integers up to $n$ are there such that $\gcd(A,B)=B$, not counting those pairs where $B^2=A$? If we consider $n = 5$ we have $25$ possible pairs. They are ...
0
votes
0answers
21 views

Determining if a rational number has a terminating decimal expansion (proof)

Theorem: $x=\frac pq$ is any given rational number, $n$ and $m$ are any whole numbers (including zero) which you can choose. a) If $q=2^n5^m$ is possible, $x$ has a terminating decimal expansion. ...
1
vote
2answers
39 views

Euler Phi of a number

I saw an AIME problem where you took $\phi(1000)$ and then divided by $2$. The problem is here: http://www.artofproblemsolving.com/community/u244443h580665p4722095 $\phi(1000)$ gives you how many ...
6
votes
1answer
50 views

Pairs of integers $(a,b)$ such that $\frac{1}{6} =\frac{1}{a} + \frac{1}{b}$

How many pairs of integers are there $(a,b)$ with $a \leq b$ such that $$\frac{1}{6} =\frac{1}{a} + \frac{1}{b}$$ My attempt: Clearing fractions we get $$ab = 6(a+b)$$ $$ \Longrightarrow ...
1
vote
0answers
38 views

Blocks of consecutive natural numbers

Let a < b be natural numbers. Prove that every block of b consecutive natural numbers contains two distinct elements whose product is divisible by ab. Suppose now a < b < c are natural ...
1
vote
1answer
41 views

If $r$ is a primitive root of an odd prime $p$, then $s$ is a residue of $p$ iff $s \equiv r^{2n} \pmod{p}$.

If $r$ is a primitive root of an odd prime $p$, then prove that $s$ is a residue of $p$ iff $s \equiv r^{2n} \pmod{p}$. The above was the original statement of an elementary number theory ...
0
votes
1answer
33 views

Prove $a^2+6a+1\perp 375$ for all $a\in \mathbb{Z}$.

Prove $A=a^2+6a+1\perp 375$ for all $a\in \mathbb{Z}$ I thought to write $375=3\cdot5^2$. So if $A$ is coprime with $3\cdot5^2$ they must share no prime factors. Then I test if $3$ or $5$ divide $A$ ...
2
votes
2answers
61 views

Prime $4n+3$ simple proof?

Let $p=4n+3$ be a prime. Prove that $\prod_{k=1}^{p-1}(x+k^2)\equiv (x^{\frac{p-1}{2}}+1)^2\pmod p$. Is there a simple proof that doesn't use say arithmetic in $\mathbb{Z}[i]$? My approach was to ...
0
votes
2answers
31 views

The Density Of The Real And Rationals

I am trying to get better understanding of the density property of the real numbers and the rational. As for the rational if we take for example $\frac{1}{100} $ and $\frac{1}{101}$ which number can ...
4
votes
1answer
46 views

Why is there only one group of order $n$ for some non-primes?

I would like to understand for which integers $n$ is there only one group of order $n$. (up to isomorphism). I understand that if $n$ is prime there is only one group of order $n$. In Sloane's OEIS ...
3
votes
3answers
90 views

Prove there exists $m > 2010$ such that $f(m)$ is not prime

Let $$f(x) = \sum_{i = 0}^n a_ix^i$$ be a polynomial with $a_i \in \mathbb Z, n > 0, a_n \neq 0$. Prove that there exists some natural number $m>2010$ such that $|f(m)|$ is not a prime number. ...
1
vote
1answer
62 views

Rational points on circle

I need help for the following questions. Give the necessary and sufficient condition for $r$ such that the circle $x^{2}+y^{2}=r^{2}$ passes the rational points. I know the obvious sufficient ...
1
vote
3answers
67 views

Solve in non-negative integers: $m^2+n^2=1997 (m-n)$

Solve in $\mathbb{N}$:$$m^2+n^2=1997(m-n)$$ I try with quadratic equation or with factorising, but I have no idea what to do after that.
2
votes
2answers
50 views

“$111 \dots$ upto $3^n$ digits” is divisible by $3^n$

Prove that an integer of the form "$111 \dots$ upto $3^n$ digits" is divisible by $3^n$ My attempt For $n=1,$ $111$ is divisible by 3. Let $T_n=111...$ upto $3^n$ digits is divisible by $3^n$. ...
6
votes
2answers
187 views
+100

diophantine equation $x^3+x^2-16=2^y$

Solve in integers: $x^3+x^2-16=2^y$. my attempt: of course $y\ge 0$, then $2^y\ge 1$, so $x\ge 1$. for $y=0,1,2,3$ there is no good $x$. so $y\ge 4$ and we have equation $x^2(x+1)=16(2^z+1)$, ...
0
votes
5answers
69 views

Mathematical induction

Prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ where $n$ is a nonnegative integer. I have seen many questions on this site that contain the answer to this problem and I already know the solution, ...
0
votes
2answers
94 views
0
votes
1answer
24 views

A question in Number Theory - prove there exist m>2010 s.t f(m) is not prime [duplicate]

Let $$f(x)=\sum_{i=0}^n a_nx^n$$ be a polynomial with $$a_n \in Z,n>0,a_n\neq0$$ Prove that there exists some natural number $$m>2010$$ such that $$|f(m)|$$ is not a prime number. I tried to ...
1
vote
0answers
59 views

Are modular Collatz graphs strongly connected?

A while ago, I stumbled on the idea of representing the Collatz function, modulo a prime $p$, as a directed graph. Define, as usual $$ T(x) = \begin{cases} (3x+1)/2 & \text{if $x$ is odd,} \\ x/2 ...
12
votes
6answers
2k views

If an inequality is true for all natural numbers, is it necessarily true for all real numbers inbetween?

A lot of the time in lectures, my professors prove (by induction) an inequality (e.g. $(1+x)^n \geq 1+nx$) in the natural numbers (or any subsets thereof), and I've noticed (not rigourously; only by ...
0
votes
1answer
35 views

A question about primes, number theory [duplicate]

I tried to solve this question but without a success: Let $p$ be a prime number,and $p^2+2$ is also prime, prove that $p=3$. I tried to show $p^2+2$ as a product of numbers and then to show that ...
0
votes
2answers
30 views

Number Theory - Multiple of $36$ problem

Let $N$ be the greatest integer multiple of $36$ all of whose digits are even and no two of whose digits are the same. Find the remainder when $N$ is divided by $1000$. $$N = \overline{abcd....} ...
1
vote
5answers
95 views

Proving $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ [duplicate]

I'm trying to prove by MI. I have already distributed n+1, but now I'm stuck on how I can show 9 divides the RHS since $42n$ and $3n^3$ does not divide evenly. ...
0
votes
3answers
401 views

Mathematical induction prove that 9 divides $n^3 + (n+1)^3 + (n+2)^3$ . [duplicate]

How can I use mathematical induction to prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ whenever $n$ is a nonnegative integer?
4
votes
5answers
4k views

Simple Proof by induction: “9 divides $n^3 + (n+1)^3 + (n+2)^3$”

I'm trying to prove using induction that 9 divides $n^3 + (n+1)^3 + (n+2)^3$ whenever $n$ is a non-negative integer. So far, I have: Base case: P(1) = (1) + (8) + (27) = 36, 36 can be divided by 9 ...
3
votes
1answer
50 views

Negative Pell's Equation: Prove that $k=3$.

I made this problem (while solving another problem) but I haven't been able to prove it. Let $x,y,k\in \mathbb{Z}^+$. Prove that if $x^2-(k^2-4)y^2=-1$ then $k=3$. Any pointers are appreciated, but ...
0
votes
1answer
33 views

Find two numbers, given their greatest common divisor and least common multiple [on hold]

Highest common factor (HCF) of two numbers is $20$. Least common multiple (LCM) of the same two numbers is $420$. Both numbers are higher than $50$. Find the $2$ numbers. I used factorising trees ...
0
votes
0answers
30 views

Is 1 the geometric mean of a positive number and its inverse? (same for -1 and neg numbers) [on hold]

Recently, I realized that all of multiplication in the interval [1, infinity) is contained as division in (0, 1} (same the other way around with neg numbers). It also seems to me that 1 is the ...
0
votes
1answer
30 views

if $a = 0 \mod p $ and $a \not = 0 \mod p ^2$

let $a = bc$ if $a = 0 \mod p $ and $a \not = 0 \mod p ^2$ with $p$ prime. what can we deduce? ($a,b,c \in \mathbb{Z}$) I have that if $a = 0 \mod p$ then either $b = 0 \mod p$ or $c = 0 \mod p$ (can ...
2
votes
3answers
152 views

Is there a compelling reason for the $lcd$ per se and $lcd\equiv lcm$ in fraction arithmetics?

I haven't done arithmetics during the past few years, so I'm filling the gaps before I'm starting out in math in a month, so I have little understanding of the numerics. I've come across such a gap ...
2
votes
1answer
55 views

Why does the graph of $y=\gcd \left(\frac{x}{y},xy\right)$ seem to have 4 “straight” lines?

Why does the graph of $y=\gcd \left(\frac{x}{y},xy\right)$ seem to have 4 "straight" lines? Using https://www.desmos.com/calculator for plotting.
-1
votes
1answer
25 views

Show all final 2-digit numbers of the decimal expansions of squares are to be found among those of $0^2, 1^2,…25^2$ [duplicate]

I'm not really sure where to begin. The first part of the question states that "every positive integer has a unique representation in the form $50k+l$, with $-24\lt l \le 25$," which isn't even true, ...
0
votes
3answers
63 views

Splitting $\frac{1}{n}$ for $n\geq 2$ as a sum of $m\geq 2$ unit fractions (Various proofs)

So the problem is to write $\frac{1}{n}=\sum_{1}^{m}\frac{1}{a_{k}}$ for $a_{k}\in \mathbb{N}$ (distinct if it is too easy). The only proof I've seen is with ...
0
votes
2answers
38 views

Show that every positive integer has a unique representation in the form $50k+l$…?

with -24 $\lt l \le$ 25. Then I need to conclude that all final 2-digit numbers of the decimal expansion of squares are to be found among those of $0^2, 1^2, 2^2,...., 25^2$. I'm thinking that I ...
0
votes
0answers
32 views

quick question about prime numbers and division

suppose that $a,b \in \mathbb{Z}$ and that $ab = kn$ where $k \in \mathbb{Z}$ and $n$ is prime. My book says that since $n$ is prime, then $ n $ divides $a$ or $n$ divides $b$. Could someone explain ...
-4
votes
0answers
68 views

Are natural integers intuitive? [on hold]

I'm not sure the following belongs on this site, since it is not a question but an idea that I would like to discuss, and since it is not maths, but rather a clumsy approach to the philosophy of ...
4
votes
5answers
100 views

Proving $6^n - 1$ is always divisible by $5$ by induction

I'm trying to prove the following, but can't seem to understand it. Can somebody help? Prove $6^n - 1$ is always divisible by $5$ for $n \geq 1$. What I've done: Base Case: $n = 1$: $6^1 - 1 = ...
1
vote
2answers
38 views

n is either a prime or has at least three prime factors

if $\phi(n) |n-1$ then n is square-free. Show also that n is either a prime or has at least three prime factors. n prime if is obvious. $\phi(p)|p-1$ since $\phi(p)=p-1$.
10
votes
1answer
99 views

Last nonzero digit of $2010!$ [on hold]

I have to calculate the last nonzero digit of $2010!$ Till now I couldn't find any pattern.
0
votes
1answer
26 views

Prove that in $\Bbb{Z}$, $\forall a,b\in\Bbb{Z}$ such that $a = bq +r$, we can find $r$ such that $-\frac{1}{2}b \leq r \leq \frac{1}{2}b$

In $\Bbb{Z}$, we know that for all $a, b \in \Bbb{Z}$, we can express $a = bq + r$ such that $|r| < |b|$. However, I read from this post Prove that the Gaussian Integer's ring is a Euclidean ...
7
votes
2answers
152 views

Solve $x^3=y^2-y+1$ in positive integers.

I recently started doing number theory and have finished with all the basic, intermediate and some of the advanced stuff with ease. However, I encountered this question and have been stuck for about a ...