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

learn more… | top users | synonyms (1)

2
votes
2answers
47 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
15 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
29 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
40 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
85 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
44 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
57 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
23 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
28 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
59 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
28 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
66 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
49 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
52 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
31 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
63 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
98 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
98 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
35 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
45 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
36 views

Number theory - Primitive roots and residue

If $r$ is a primitive root of odd prime $p$, then prove that $s$ is a residue of p iff $s \equiv r^{2n} \ (\mod p)$. The above was the original statement of an elementary number theory question, the ...
0
votes
0answers
17 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
136 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
36 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
35 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
36 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
85 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
53 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
68 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
29 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 ...
4
votes
5answers
247 views

Show that the numbers $(2n + 1)$ and $(4n^2+1)$ are relatively prime

How can I show that $(2n + 1)$ and $(4n^2+1)$ are relatively prime for all $n$? I know the use of $ax + by = 1$ to show $x,y$ to be relatively prime, but how can I apply that here?
0
votes
1answer
17 views

Percentage increases, decreases [duplicate]

Why does a % decrease of a number not equal the same % increase when you reverse the calculation? ie: $30 less 20% = $24.00 Reverse calculation $24 plus 20% = $28.80 Please explain
1
vote
1answer
57 views

How to show infinite square-free numbers?

Here's the exact wording of the problem: "The squares, of course, are the numbers 1,4,9,... The square-free numbers are the integers 1,2,3,5,6,... which are not divisible by the square of any prime ...
2
votes
2answers
28 views

Prove that $N$ is composite if and only if $p|N$ for some $p$ prime, $p\leq \sqrt{N}$.

Show that $N$ is composite if and only if $p|N$ for some $p$ prime, $p\leq \sqrt{N}$ I have absolutely no idea on how to start this, could you guys give me some tips? I'll update if I can come up ...
1
vote
1answer
36 views

If $\gcd(m,n)= 1$ and $n \leq km$ and $m \leq kn$

If $\gcd(m,n)= 1$ and $n \leq km$ and $m \leq kn$ I want to prove that $ mn \leq k$ If I multiply the first inequality by $m$ I will get that $mn \leq km^2$ And If I multiply the second inequality ...
-2
votes
2answers
32 views

How do you show that$ ∏j ≡1 $(mod p) where j is $1 \le j\le p-1$ and $\frac{j}{p}=1$

Also, $P$ is a prime of the form $4k+3$ and $k$ is an element of natural numbers including $0$.($\frac{j}{p}$) denotes a legendre symbol.
2
votes
1answer
34 views

How to determine number of roots of $a^k + b^k \equiv c^k \pmod{d}$?

Is there a way to determine number of roots of $a^k + b^k \equiv c^k \pmod d$? It is an algorithmic task, not theoretic math. I am not looking for a closed formula.
2
votes
0answers
24 views

Find number of $r$-element subset of $S$ satisfying a property

Let $S= \{1,2,...,1990\}$. A $31$-element subset $A$ of $S$ is said to be good if the sum of all the elements of $A$ is divisible by $5$. Find the number of $31$-element subsets of $S$ which are good. ...