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

learn more… | top users | synonyms (1)

0
votes
3answers
28 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}{(n-1)n}$ = $\frac{(n-1)}{n}$ using induction. I am getting stuck midway through the inductive step. Here is what I have: ...
0
votes
2answers
22 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$$ ...
0
votes
0answers
20 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. ...
0
votes
2answers
14 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.
1
vote
2answers
35 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
48 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 ...
0
votes
0answers
25 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 ...
0
votes
1answer
29 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
57 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
1answer
20 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?
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
43 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
89 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. ...
2
votes
2answers
49 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$. ...
1
vote
3answers
66 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.
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 ...
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....} ...
0
votes
1answer
61 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 ...
0
votes
0answers
29 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 ...
0
votes
5answers
68 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, ...
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 ...
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
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
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
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
65 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 ...
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.
4
votes
5answers
99 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
votes
0answers
24 views
0
votes
3answers
15 views

system of conguences

I am trying to figure out how to solve: Find $x, y \in \mathbb{Z}$ such that $$2x+y\equiv 4\pmod{17}$$ and $$5x-5y\equiv 9\pmod{17}.$$ I know this means $2x+y-4$ and $5x-5y-9$ are multiples of $17$, ...
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 ...
4
votes
1answer
36 views

Find all the primes $p,q$ such that $2^{p-q}+1\equiv0\pmod{pq}$

Find all the primes $p,q$ such that $2^{p-q}+1\equiv0\pmod{pq}$ I'm not sure how to start this. I am guessing Fermat's little theorem has something to do with this as $2^p\equiv 2\pmod{p}$ and ...
5
votes
0answers
47 views

An Impossible Sequence of Prime Powers

Let $x_1,x_2,\ldots$ be a sequence of positive integers that satisfies the recurrence relation $$x_{n+1}=2x_n(x_n-1)+1$$ for all positive integers $n$. It seems impossible that every term in this ...
2
votes
1answer
37 views

Proving $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 [duplicate]

I am trying to prove that $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 for all $k \in Z$. I am not even sure what tags to use because I am not sure of right methods to ...
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
0answers
19 views

Question related to image of $[1,N]^n$ under a linear tranformation

I am reading an article and I am a bit confused about the following passage. I would appreciate any clarification. It goes as follows: Let $\bar{F}$ be a collection of $r$ linearly independent ...
9
votes
3answers
142 views

Sum of digits of $11\dots 11^2$ where $11\dots 11$ is a 1992 digit number with all digits $1$ [duplicate]

I read this on a non-math forum where the OP says this is a question for Grade 6 elementary school students. Grade 6 elementary school level is somehow ambiguous but clearly this means no advanced ...
0
votes
0answers
38 views

Seeking Recommendation on Number Theory textbooks [on hold]

S.E advisers, I am a college sophomore with double majors in mathematics and Russian language. I wrote this email to seek a recommendation on good introductory textbooks for number theory. I will ...
3
votes
1answer
36 views

Decide if there exist $a$ and $b \in \mathbb{Z}$ such that $a^2=2b^2$.

Decide if there exist $a$ and $b \in \mathbb{Z}$ such that $a^2=2b^2$. $a,b \neq 0$ We have to solve this kinds of problems using the order of a prime function: $v_p(a) \in \mathbb{Z}$ which tells ...
1
vote
1answer
34 views

Exact conditions under which the arithmetic progression $\{bk + r\}_{\{k\in\mathbb{N}\}}$ contains 0,1, or 2 primes

Suppose that $p$ is prime, and $p|b$ and $p|r$, where $0\leq r<b$. Here's what I've tried: If $r|b$, then $r\neq 1$ (since otherwise $p=1$, a contradiction), so $bk+r = (cr)k+r$ for some integer ...
1
vote
2answers
32 views

Existence of square root in $\mathbb Z_n$?

I had this question on my final exam and I struggled with it. It asks to prove or disprove the following: $$\forall m \in Z, \ \forall \ [a] \in Z_{m}, \ \exists \ [b] \in Z_{m}, [a]=[b]^{2} $$ ...
1
vote
1answer
38 views

How do I solve these questions using Diophantine equations?

I have been told that it is easier to solve the below 2 questions using Diophantine equations instead of simply trial and error. 1) Find the smallest positive integer which, when divided by 6, ...
1
vote
5answers
86 views

Sum of the last four digits of $3^{2015}$

If $N = 3^{2015}$, what is the sum of the last four digits of $N$? $(A)21$ $(B)22$ $(C)23$ $(D)24$ It is not possible using a calculator, so how can I do it? Hints are appreciated.
0
votes
1answer
55 views

Where to make induction?

I have read a exercise that states as follows; Use induction to prove that $\forall n \in \mathbb{N}: \forall m \in \mathbb{N}: n<m \Rightarrow \exists r \in \mathbb{N}: n+r=m.$ Sugestion. ...
2
votes
3answers
71 views

$5 \nmid 2^{n}-1$ when $n$ is odd

I want to prove that $$5 \nmid 2^{n}-1$$ where $n$ is odd. I used Fermat's little theorem, which says $2^4 \equiv 1 \pmod 5$, because $n$ is odd then $4 \nmid n$ , so it is done. can you check it ...
1
vote
1answer
30 views

Euler's Totient function $\forall n\ge3$, if $(n-\phi(n)) = \sqrt{n}\ $,$\ $then $(n-\phi(n)) \in \Bbb P$

Recently I opened a question about what it might be a new property of Euler's Totient function. I am still studying the Totient function and I found another interesting relationship, it is very ...