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

learn more… | top users | synonyms

4
votes
0answers
39 views

Number Theory; Digits summing to 225

How many digits are in the smallest multiple of 225 whose digits sum to 225? I wasn't sure how to appraach this problem; it seems the sum of the digits doesn't have much relation to it being a ...
2
votes
1answer
27 views

Number Theory: Let $m = 2^ap_1^{b_1}p_2^{b_2}…p_r^{b_r}$ where $a\geq 0,r \geq 0, b_i \geq 1$.

I need to find how many incongruent solutions exist to the equation: $x^2 \equiv 1(mod\space m)$. I'm thinking I need to take a case by case approach, for example when $a = 0$, but these number ...
3
votes
3answers
35 views

$d(n)$ is odd if and only if $n = k^2$

Can someone help me prove that $d(n)$ is odd if and only if $n = k^2$ for some integer $k$? For reference: $d(n)$ gives the number of positive divisors of $n$, including $n$ itself.
-1
votes
1answer
38 views

Find an $n$ not a power of a prime such that $n$ has 51 positive divisors [on hold]

Find an $n$ not a power of a prime such that $n$ has 51 positive divisors. I'm not sure where to even start with this question. Any help would be really appreciated.
3
votes
3answers
38 views

Proving $ab(a+b)+ac(a+c)+bc(b+c)$ is even

Prove that $\forall a,b,c\in \mathbb N: ab(a+b)+ac(a+c)+bc(b+c)$ is even I tried to simplify the expression to something that would always yield an even number: $ (a+b+c)(ab+ac+bc)-3abc$ but ...
0
votes
1answer
20 views

Give an example of three positive integers m, n, and r

Can someone give an example of three positive integers m, n, and r, and three integers a, b, and c such that the GCD(m,n,r) = 1, but there is no simultaneous solution to: x ≡ a (mod m) x ≡ b (mod n) x ...
0
votes
2answers
37 views

Twin Primes Problem: Need Help

Are there any twin primes of the form $2^n − 1$, $2^n + 1$, for $n > 2$? If so, can someone give me an example, and if not, can someone prove why there aren’t any.
1
vote
0answers
19 views

Number theory: show that ${ 1^2, 2^2, 3^2,… , m^2}$ cannot be a complete residue system

Is this an acceptable answer? Question: show that ${ 1^2, 2^2, 3^2,... , m^2}$ cannot be a complete residue system. Since the above has $m$ elements, one must show it cannot be a complete residue ...
0
votes
1answer
20 views

Proving a number doesn't divide another and proving $lcm$ using the definition

Say I have two integers $a,b$ and I want to prove that $a\not \mid b$ or $ak\neq b$, do I have to take two adjacent $k$s such that $ak_1 < b$ and $ak_2> b$? Is there another way? Another ...
1
vote
4answers
36 views

Proving that if $8\mid (n^2+2n)$ then $2\mid n$

Let $n\in \mathbb N$ prove that if $8\mid (n^2+2n)$ then $2\mid n$. From the given, there exsits $k\in \mathbb N$ such that $8k= (n^2+2n)$, take $k=1$, and we get $2\cdot 4 = n(n+2)$. Now my ...
6
votes
3answers
431 views

How many 0's are in the end of this expansion?

How many $0's$ are in the end of: $$1^1 \cdot 2^2 \cdot 3^3 \cdot 4^4.... 99^{99}$$ The answer is supposed to be $1100$ but I have absolutely NO clue how to get there. Any advice?
0
votes
3answers
65 views

Find all integers $x$ such that $x^2+3x+24$ is a perfect square.

Find all integers $x$ such that $x^2+3x+24$ is a perfect square. My attempt: $x^2+3x+24=k^2$ $3(x+8)=(k+x)(k-x)$ Now, do I find solution treating cases? But that doesn't seem very easy. ...
5
votes
2answers
54 views

Elementary number theory , when is $12n^2 + 1$ a square

Prove that if $$k = 2 + 2\sqrt{12n^2 + 1}$$ is an integer then it is a square. Can anyone help me with this? All I know is that k is an integer if and only if ${12n^2 + 1}$ is a square. What do I ...
4
votes
0answers
64 views

Is the Wikipedia article on the proof for Bertrand's Postulate correct?

I was checking out the Wikipedia article on the proof of Bertrand's Postulate. For Lemma 4, the argument is made for $x\ge 3, x\#<2^{2x-3}$ Here's the proof by induction: $n = 3$: $n\# = ...
5
votes
0answers
67 views

Olympic number theory problem: is this solution fine and sufficiently well written?

Determine all the positive integers $m$ such that both the ratios $$ \frac{2(5^m+5)}{3^m+1}, \frac{9^m+1}{5^m+5}$$ are integers. Attempt to a solution: If the ratios are both integers, than their ...
1
vote
2answers
34 views

Let $k \geq 2 \in \mathbb{N}$ Show that each of $k! +2, k! +3, … , k! +k$ is composite.

Let $k \geq 2 \in \mathbb{N}$ Show that each of the numbers $k! +2, k! +3, ... , k! +k$ is composite. So, firstly I'm not sure I fully understand the question. Surely let $k = 2$ then $2!+3 = 5$, ...
1
vote
2answers
49 views

There does not exist a polynomial $p(x)$ with integer coefficients which gives a prime number $\forall x\in \mathbb{Z}$ [duplicate]

There does not exist a polynomial $p(x)$ with integer coefficients which gives a prime number $\forall x\in \mathbb{Z}$ My attempt: I defined a polynomial as ...
4
votes
5answers
94 views

Prove that the equation $a^2+b^2=c^2+3$ has infinitely many integer solutions $(a,b,c)$.

Prove that the equation $a^2+b^2=c^2+3$ has infinitely many integer solutions $(a,b,c)$. My attempt: $(a+1)(a-1)+(b+1)(b-1)=c^2+1$ This form didn't help so I thought of $\mod 3$, but that didn't ...
1
vote
1answer
22 views

Show that in an integral right angled triangle, area is not perfect square.

Show that in an integral right angled triangle, area is not perfect square. I tried a few things, one of the being using the stereotype pythagoras form of the number, and tried drawing a few squares, ...
3
votes
1answer
38 views

Let $p$ be a prime. Show that ${n \choose p}-\bigl[\frac{n}{p}\bigr]$ is divisible by $p$, for all $n\in \mathbb{N}$ [duplicate]

Let $p$ be a prime. Show that $${n \choose p}-\bigg[\dfrac{n}{p}\bigg]$$ is divisible by $p$, for all $n\in \mathbb{N}$. I could not attempt this problem at all. Please help. Thank you. EDIT: Here ...
3
votes
1answer
24 views

Let $\{a_n\}$ be the sequence of positive integers defined by $a_n=20+n^2$.Set $d_n=\gcd(a_n,a_{n+1})$. Show that $d_n\mid 81$, also… [duplicate]

Let $\{a_n\}$ be a sequence of positive integers defined by $a_n=20+n^2$. Set $d_n=\gcd(a_n,a_{n+1})$. Show that $d_n\mid 81$ and also find all possible values of $d_n$. Show that each of those values ...
0
votes
4answers
48 views

Divisibility. $k= \frac{3^{77}-1}{2}$ [on hold]

How to prove that: $$ k= \frac{3^{77}-1}{2}$$ is not prime and $2$ doesn't divide $k$? And second: How to prove that $10$ doesn't divide: $321^{654} + 123^{456}$
0
votes
1answer
25 views

Show that $x^4 \equiv -1\pmod p $ is solvable $\iff $ $ p \equiv 1 \pmod 8$

Show that $x^4 \equiv -1 \pmod p $ is solvable $\iff $ $p \equiv 1 \pmod 8$ My attempt : $p$ must satisfy $(-1)^{(p-1)/d}\equiv 1 \pmod p$, where $d = \gcd(4,p-1)$ but I still don't see how this ...
3
votes
1answer
77 views

If $N=a^2+b^2=c^2+d^2$ then $N$ cannot be a prime number.

The problem says that if $N$ can be expressed in two ways as the sum of two squares then $N$ is not prime. Clearly the first idea is to try and express $N$ as a product of two expressions containing ...
2
votes
1answer
32 views

$S=\{0,1,2,…,q^2-1\}$, is there a way to figure out how many elements contained in $S$ can be written as the sum of $2$ squares?

I'm currently working on a proof, and have broken it down into a series of problems. I've had success with every part except one. My question is (and it may be really easy; it's getting late): 'Let ...
4
votes
0answers
18 views

Sequence of non-collinear integer points.

This is a question from a British Olympiad, I've completed the first 3 but this one had me rather stumped. Given two points $P$ and $Q$ with integer coordinates, we say that $P$ sees $Q$ if the ...
2
votes
3answers
57 views

Determine the integers $a$ such that the congruence $x^4 \equiv a \pmod p$ has a solution for $p = 7, 11, 13$

Determine the integers $a$ such that the congruence $x^4 \equiv a \pmod p$ has a solution for $p = 7, 11, 13$ This looks similar to previous problem but kinda tricky. I'm not sure where to ...
5
votes
1answer
207 views

If $a^2 + p^2 = b^2$ then $2(a+p+1)$ is a perfect square

We are given $$ a^2 + p^2 = b^2 $$ where $a,b\in\mathbb{Z}$ and $p$ is prime. We are to show that $$2(a+p+1)$$ is a perfect square. Is there any elegant ways to go about this problem? Struggling to ...
16
votes
3answers
724 views

Can Number Theory be visualized?

So I was thinking about a hard euclidean geometry problem, when it hit me just how much more difficult it would become without the aid of a diagram. This got me thinking: Wouldn't it be great if we ...
1
vote
2answers
28 views

Determine the integers $a$ such that the congruence $ax^4 \equiv b \pmod{13}$ has a solution for $b = 2, 5, 6$

Determine the integers $a$ such that the congruence $ax^4 \equiv b \pmod{13}$ has a solution for $b = 2, 5, 6$ I think the problem wants $a$'s that work for all $b=2,5,6$. Can I please have a ...
0
votes
0answers
14 views

$x ≡ a \pmod{m}, x ≡ b\pmod{n}, x ≡ c\pmod{r}$ [duplicate]

What could be an example of three positive integers $m, n$, and $r$, and three integers $a, b$, and $c$ such that the $\mathrm{gcd}$ of $m, n$, and $r$ is $1$, but there is no simultaneous solution to ...
1
vote
1answer
40 views

$d(n)$ is odd iff $n = k^2$ [duplicate]

The function $d(n)$ gives the number of positive divisors of $n$, including $n$ itself. For example, $d(25) = 3$ because $25$ has three divisors: $1$, $5$, and $25$. Prove that $d(n)$ is odd if and ...
9
votes
0answers
41 views
+50

A number $n$ which is the sum of all numbers $k$ with $\sigma(k)=n$?

For a positive integer $n$, let us define a set $$A_n = \{ k\in\mathbb{N} \mid \sigma(k) = n \}$$ where $\sigma$ is the divisor-sum function (a well-known multiplicative number-theoretic function). ...
3
votes
1answer
65 views

Euler's function $\phi$: Values such that $\phi(n)=8$, $\phi(n)=14$

Let $\phi(n) $ be Euler's Totient Function Let us consider $$ |\{ n \in \mathbb{N} : \phi (n) = 8 \} | = 5, $$ and $$ |\{ n \in \mathbb{N} : \phi (n) = 14 \} | = 0. $$ How would I go about ...
4
votes
2answers
73 views

Starting with $13^{2013}$ can we get $2013^{13}$ by the following process.

This is the problem that I found in a question paper. The problem is: A positive integer is written on the board. We repeatedly erase its unit digit and add 4 times that digit to what remains. ...
1
vote
0answers
28 views

elementary number theory exercise 2.22 [on hold]

let $X_n$=$p_1$$p_2$...$p_n$ and $a_k$=$1+kX_n$ where $p_1$up to $p_n$ are prime numbers and $k$ ranges from $1$ to $n-1$ , show that if $i$ is not equal to $j$ then gcd of $a_i$ and $a_j$ is equal to ...
4
votes
1answer
40 views

Show that $\mathrm{gcd}(x+4,x-4)$ divides $8$ for all integers $x$.

I want to prove that $\mathrm{gcd}(x-4,x+4)$ divides $8$ for all $x\in \mathbb{Z}$ Since they are both polynomials of degree $1$, it suggests that the $\mathrm{gcd}$ is a constant. Using Euclidean ...
0
votes
1answer
42 views

If $2^{k} + 1$ is prime, prove that $k$ has no other prime divisors than $2$. [duplicate]

I am trying to prove this by contradiction: Assume $2^{k} + 1$ is prime. By definition of odd number $2^{k} + 1$ is odd because $2^{k} + 1 = 2\cdot 2^{k-1} + 1$ Then $2^{k} + 1 \pmod{2} \equiv 1 ...
11
votes
2answers
132 views

When is $2^n -7$ a perfect square?

This came up while solving another ENT problem. I want to ask when is: $$2^n -7 \text{ where } n\geq 3$$ a perfect square? Specifically, I also wanted to know what would be the solutions when $n$ is ...
0
votes
0answers
23 views

Number of solutions of the congruence, $x-y \equiv z \pmod{n}$, where $x,y$ in a set contain less than $n$ and relatively prime to $n$? [on hold]

I known number of solution of the congruence, $x+y \equiv z \pmod{n}$,$x,y\in U_{n}$ is $N(z)=n\prod_{ p\backslash n}\left(1-\frac{\varepsilon(p)}{p}\right)$, ...
0
votes
3answers
33 views

Proving if $p|ab$ then $p|a\vee p|b$, then $p$ is prime

Let $1\neq p\in \mathbb N$ such that $\forall a,b \in \mathbb N$ if $p|ab$ then $p|a\vee p|b$. Prove that $p$ is prime. My attempt, proof by contradiction: Suppose $p$ isn't prime, then ...
-2
votes
3answers
62 views

A number that leaves a remainder of $1$ when divided by $2,3,4,5,6,7$ [on hold]

What is a number that when divided by $2,3,4,5,6,7$ leaves a remainder of $1$? I have tried some sample numbers, but I am interested in a general solution. Any ideas?
0
votes
1answer
10 views

A limited composition of two unlimited functions on natural numbers?

Can someone give an example of two functions $f,g:\Bbb N\to \Bbb N$ such that $|\operatorname{Im}f|,|\operatorname{Im}\,g|\notin\Bbb N$, but such that $|\operatorname{Im}\,g\circ f|\in\Bbb N$?
0
votes
1answer
18 views

Finding a module for the series $2^{i}$ from 0 to 219

How can I compute this: $\{ \sum 2^{i}$ for $i \in [0, 219] \} \pmod{13}$ I tried to manipulate the series by using the root principle to find the number of elements divisible by every prime $\leq ...
0
votes
5answers
75 views

Prove that if you divide $10^n$ by $9$ then the remainder is $1$

$n=1$ Then $\frac{10^1}{9} = \frac{10}{9}$ remainder = $1$. For $n\geq2$, how does you do this? I want to prove that last digit is always zero, of $10$ raised to power. How do I do that please by ...
2
votes
2answers
48 views

Product of Divisors of some $n$ proof

The function $d(n)$ gives the number of positive divisors of $n$, including n itself. So for example, $d(25) = 3$, because $25$ has three divisors: $1$, $5$, and $25$. So how do I prove that the ...
2
votes
2answers
19 views

Need Verification on a Modulus Proof

So basically I have to prove: n ≡ 1 (mod 4) if and only if n ≡ 1 (mod 8) or n ≡ 5 (mod 8). Is this a sufficient proof: $4 \times 2n + 1= 8 \times n + 1 \equiv 1 \pmod {8}$ where $n$ is an integer ...
1
vote
1answer
24 views

Primitive Roots Modulo $2^n$ for $n\geq3$

Question: (a) Prove that there is no primitive root modulo $2^n$ for any $n\geq3$, where $\bar{a}\in(\mathbb{Z}/2^n\mathbb{Z})^\ast$ is a primitive root modulo $2^n$ if the order of $\bar{a}$ is ...
0
votes
1answer
13 views

GCD of 1: Prove set is Complete Residue System Proof [on hold]

Suppose that $m$ and $n$ are integers with greatest common divisor $1$. Assume that both are greater than $1$. Prove that the set ${0 · n, 1 · n, 2 · n, . . . ,(m − 1) · n}$ is a complete residue ...
1
vote
1answer
49 views

Is the solution to this elementary number theory problem correct?

Problem: A natural number $n$ is called nice if the following properties hold: • The expression is made ​​up of 4 decimal digits; • the first and third digits of $n$ are equal; • the second and ...