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

learn more… | top users | synonyms (1)

0
votes
1answer
14 views

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

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
33 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
27 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
0answers
42 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
29 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
64 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
46 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
57 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
95 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
14 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
44 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
33 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
134 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
52 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
67 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
28 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
33 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. ...
1
vote
0answers
56 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 ...
0
votes
1answer
63 views

Consider the following expression about natural number: $\forall n\exists m: m^{2}=n$

I understood the first part and made an attempt. Then the question asked me to demonstrate an expression about natural numbers of my own which has an opposite truth value to the one above and explain ...
0
votes
1answer
41 views

Number of solutions of the congruence $x^p \equiv x\pmod p$

How do I show that $x^p \equiv x\pmod p$ has precisely $p$ solutions? I can use Lagrange's theorem and Fermat's little theorem.
0
votes
2answers
35 views

Prove if the following is true or provide a counterexample if it is not

For all sets A and B, |P(A × B)| $\ne$ |P(A) × P(B)| My first instinct is that it is false and I picked sets like A = {1}, B = {2} but when you write out the power set of these sets you end up with ...
7
votes
0answers
98 views

Euler's Totient function $\forall n\ge3$, if $(\frac{\varphi(n)}{2}+1)\ \mid\ n\ $ then $\frac{\varphi(n)}{2}+1$ is prime

While I was studying Euler's Totient function, $\varphi(n)$, I stumbled upon the marvelous book "Index to Mathematical Problems, 1980-1984" By Stanley Rabinowitz. In this page of the book (link to ...
0
votes
0answers
20 views

Greatest divisor of N less than square root of N (given prime factorization) [on hold]

If I know the prime factorization of some number N, how can I mathematically find, with proof, the greatest divisor of N (doesn't necessarily have to be prime) that is less than the square root of N?
2
votes
0answers
154 views

Numbers $717, 71717, 7171717,\dots$ and primality

Prove or disprove that all numbers $717, 71717, 7171717,\dots$ are composite. This is related to this question. $\begin{array}\\ 717 &= \text{div by 3}\\ \color{blue}{71717} &= 29\cdot ...