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

learn more… | top users | synonyms (1)

5
votes
2answers
96 views

Aren't there obvious patterns in the primes that no one makes use of and what about this…

Let's take the sequence of naturals at or above two: $2, 3, 4, \dots$ and cross out just the primes $2,3$ and all their multiples: $\not{2}, \not{3}, \not{4}, 5, \not{6}, 7, \not{8}, ...$. Well if ...
1
vote
2answers
35 views

How to solve equations of the type: $\phi(n)=m$?

How to solve equations of the type: $\phi(n)=m$? I have, for instance, $\phi(n)=6$. I never saw that kind of questions. I would really appreciate any lead on it.
0
votes
1answer
37 views

Are $x$ and $y$ divisible by $n$, if so how do I prove it?

If $y$, $x$,are natural numbers, and $n$ is a prime number, $y = x + n$, $y>x>n$, and $y$ and $x$ are not coprime, is it true that $n$ is a divisor of both $x$ and $y$? If so could you please ...
0
votes
0answers
17 views

How do Quadratic Fields look on Complex Planes [duplicate]

I have spent a long time trying to seek some information of quadratic fields. Can someone show me a complex plane around the origin, with the points on the part of the complex plane which are ...
10
votes
0answers
45 views

Finding triplets $(a,b,c)$ such that $\sqrt{abc}\in\mathbb N$ divides $(a-1)(b-1)(c-1)$

When I was playing with numbers, I found that there are many triplets of three positive integers $(a,b,c)$ such that $\color{red}{2\le} a\le b\le c$ $\sqrt{abc}\in\mathbb N$ $\sqrt{abc}$ divides ...
0
votes
2answers
19 views

If every prime that divides $n$ also divides $m$, show that $\phi(mn)=n\phi(m)$ & $\phi(mn)=m\phi(n)$

If every prime that divides $n$ also divides $m$, show that $\phi(mn)=n\phi(m)$ & $\phi(mn)=m\phi(n)$ My attempt. As every prime that divides $n$ also divides $m$ implies $(m,n)=d$ where ...
2
votes
1answer
33 views

Largest possible subset primes

Let $q$ be a Sophie Germain prime number, i.e. $2q+1=p$ is prime. Consider the set $\{1,2,3,\ldots,p-1\}$. Then what is the maximum size of a subset of this set, such that the subset contains no two ...
1
vote
0answers
31 views

Quadratic Field of $Q[√−1]$…

Can someone show me a complex plane around the origin, with the points on the part of the complex plane which are quadratic integers in $Q[√−1]$. Another graph for $Q[√−3]$. And another for $Q[√−5]$. ...
1
vote
3answers
40 views

Prove that $\phi(n)=\frac{n}{2}$ iff $n=2^k$ for some integer $n$

Prove that $\phi(n)=\frac{n}{2}$ iff $n=2^k$ for some integer $n$ Attempt: Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Then $\phi(n)=\frac{n}{2} \implies ...
0
votes
1answer
19 views

Primes in Quadratic Fields with Norm less than 6

What are the primes in $\mathbb Q[\sqrt{−1}]$ which have norm less than $6$? Also what primes in $\mathbb Q[\sqrt{−3}]$ have norm less than $6$, and the primes in $\mathbb Q[\sqrt{−5}]$? Which of them ...
-4
votes
2answers
37 views

mathematical calculation problems [on hold]

I have been given the odd numbers $1, 3, 5, 7, 9, 11, 13, 15$ with the challenge of selecting any 3 numbers from the above, to produce the number $30$. We can perform any operation on numbers and ...
0
votes
1answer
21 views

Show that $ζ$ is a Quadratic Integer in $Q[\sqrt{−3}]$

So in the complex plane, there are three cube roots of one. Suppose we let $ζ$ be the cube root of one which has positive imaginary part. How can we show that $ζ$ is a quadratic integer in ...
5
votes
2answers
116 views

What is the ten's digit of $7^{7^{7^{7^7}}}$

What is the ten's digit of $\zeta=7^{7^{7^{7^7}}}$. I got this question while doing binomial theorem. I think that $7^4=2401$ and we only need $\zeta\pmod{100}$. All I could think of is already ...
1
vote
1answer
52 views

How Deficient a Number is? (Finding numbers having a certain deficiency)

This question was edited, in particular equations were corrected: A number N is said to be deficient by an integer $d$ if: $\sigma(N)=2N-d$ Note that powers of 2 are deficient by 1. While a prime ...
11
votes
1answer
153 views

A proof involving the Euler phi function

Problem: Let $\varphi$ be the Euler phi function, where for any $n \in \mathbb{Z^+}$, $\varphi(n)$ is the number of positive integers less than $n$ that are relatively prime with $n$. ...
-1
votes
2answers
47 views

Solving $a^2$ $+$ $ b^2$ $=$ $2c^2$ [on hold]

I was working through some number theory problems , when I came across the following question : Find all solutions of $a^2$ $+$ $b^2$ $=$ $2c^2$ Can someone help me out ? Maybe a hint ...
9
votes
4answers
341 views

Understanding the trivial primality test

I'm reading an algorithms book and I came across a code example for a primality test. The problem is that I couldn't understand the condition for the for-loop: ...
1
vote
1answer
35 views

How can I find the common solution for the following linear congruences : [on hold]

How can I find the common solution for the following linear congruences : $1.)$ $x \equiv 5 \pmod {13}$ $x \equiv 3 \pmod {12}$ $x \equiv 2 \pmod{35}$ $2.)$ $x \equiv 2 \pmod{35}$ $x \equiv ...
7
votes
3answers
100 views

Irrational Numbers : Show that $0.1248163264…$ is irrational

I was working through some basic Number Theory Problems in Rosen and came across the following problem : Show that the real number $0.1248163264...$ represented in ...
0
votes
3answers
36 views

Diophantine Equations : Solve $a^2 + b^2 = 4c + 3$

I was working my way through some number theory problems , when I came across the following question : Find all solutions to the equation $a^2 + b^2 = 4c + 3$ My Solution (partial) : If ...
8
votes
2answers
108 views

Divisibility of $6^{2^n}+ 8^{2^n} +12^{2^n}+14^{2^n}+16^{2^n}+18^{2^n} +24^{2^n} +28^{2^n}+42^{2^n}$

Prove or disprove that for all natural $n$ $$6^{2^n}+ 8^{2^n} +12^{2^n}+14^{2^n}+16^{2^n}+18^{2^n} +24^{2^n} +28^{2^n}+42^{2^n}$$ is divisible by $259$. I tried to apply mathematical induction, but ...
-1
votes
3answers
46 views

basic word problem! [on hold]

Find the smallest number by which $108$ must be multiplied to give a multiple of $80$.
4
votes
3answers
33 views

Largest subset with no arithmetic progression

I am trying to find some weak bounds on the largest subset of a set, such that the subset has the property that it contains no three elements in arithmetic progression. The elements of the original ...
0
votes
3answers
40 views

Number of times $2^k$ appears in factorial

For what $n$ does: $2^n | 19!18!...1!$? I checked how many times $2^1$ appears: It appears in, $2!, 3!, 4!... 19!$ meaning, $2^{18}$ I checked how many times $2^2 = 4$ appears: It appears in, ...
1
vote
3answers
41 views

How to apply Chinese Remainder Theorem for $x$

If: $$x \equiv 0 \pmod{17}$$ and $$x \equiv -1 \pmod{9}$$ Then how is: $$x \equiv 17 \pmod{153}$$ I get that since $\gcd(9, 17) = 153 $ the solution will be $\pmod{153}$ but how do you get the $17 ...
2
votes
2answers
68 views

Let $m$ be the least positive integer divisible by $17$ whose digits sum to $17$. Find $m$.

Let $m$ be the least positive integer divisible by $17$ whose digits sum to $17$. Find $m$. $m$ is a 3 digit number (because this was an AIME problem). $$m \equiv 0 \pmod{17}$$ $$m \equiv 17 ...
5
votes
5answers
74 views

solutions such that a combination number is odd

Let $m$ be a positive integer. Given $m$, I want to find the largest $n$, $1\leq n\leq m$, such that $$m+n\choose n $$ is odd. Is there any standard theorems or results? Any references? Thanks!
2
votes
3answers
65 views

$a^2 = 2b^3 = 3c^5$ Find the smallest value of $abc$.

We have following equation: $a^2 = 2b^3 = 3c^5$ Where $a, b, c$ are natural numbers. Find the smallest possible value of product $abc$.
1
vote
1answer
23 views

Number of $q$-th residues modulo $n$

Let $q$ be a prime and $n\ge 2$ an integer. Moreover, define $f_q(n)$ as the number of $q$-th residues modulo $n$. Is it true that if $K$ is a positive constant then there exist infinitely many $n$ ...
1
vote
4answers
54 views

Is $\gcd(2^{2n}+1, 3)=1$?

Can any one prove that $2^{2n}+1$ and $3$ are relatively prime for any integer $n$? I tried with a Matlab program and computed this gcd upto $n= 25$. I got 1 for all of them. So I suppose that the ...
3
votes
12answers
2k views

Measure 11 liters using bottles of 16, 6, and 3 liters

This question has been bugging me for a day and finally I gave up and decided to ask the community for it so here's how it goes: Suppose we have 3 bottles with capacities of $16,6$ and $3$ liters, ...
0
votes
2answers
46 views

Construction of Natural Numbers

I am trying to prove that the natural numbers can be constructed from the product of a power of $2$ and an odd number. For all $n \neq 0$ in the natural numbers, $n = (2k+1)(2^p)$, where $k$ and $p$ ...
5
votes
0answers
81 views

A problem about $e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$

Let $\alpha_i\in [0,1),\; i\in \{1,\cdots,N\}$ for some positive integer $N$, such that $$e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$$ and if for any non-empty proper subset ...
0
votes
2answers
60 views

Find all solutions of equation $x^{23}=5$ in $\Bbb Z_{23}$

I just found that $5$ is a solution by using Fermat's theorem. But, I am not sure whether there are more solutions and how I could find them...
23
votes
3answers
2k views

Is it possible for integer square roots to add up to another?

I initially was wondering if it were possible for there to be three $x,y,z \in \mathbb{Q}$ and $\sqrt{x},\sqrt{y},\sqrt{z} \notin \mathbb{Q}$ such that $\sqrt{x} + \sqrt{y} = \sqrt{z}$. I had ...
1
vote
1answer
167 views

Isn't really a monotonic sequence?

First, I'd to say that I'm a beginner so may you answer easily plz. I'll expose you the problem: I was looking up on this page http://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF and find ...
0
votes
0answers
41 views

Prove that if $(n-1)!\equiv-1 \mod n$ then $n$ is prime. [duplicate]

Let n be a natural number, $n\ge 2$. Prove that if $(n-1)!\equiv-1 \mod n$ then $n$ is prime. I tried few things but I my skills in equations modulo $n$ are not well enough. I would really appreciate ...
4
votes
2answers
106 views

How do I prove that $ f(n) = (n + 1)! - 1 $ is an injective function?

I have this problem: Consider the function $f : \mathbb{N} \rightarrow \mathbb{N}$ defined, for every $n \in \mathbb{N}$, by $$f(n) = (n+1)! - 1$$ Prove that $f$ is injective. How do I ...
0
votes
2answers
18 views

Sum of polynomial coefficient

Steve says to Jon, "I am thinking of a polynomial whose roots are all positive integers. The polynomial has the form $P(x)=2x^3-2ax^2+(a^2-81)x-c$ for some positive integers $a$ and $c$. Can you ...
2
votes
2answers
35 views

How many distinct numbers can I get mod 8

so I have the following $(0,1\ \text{or}\ 4)+(0,1\ \text{or}\ 4)+(0,1\ \text{or}\ 4)$ I want to see how many distinct numbers can I get mod $8$ by adding from this list 3 times for example I got so ...
1
vote
3answers
38 views

Given $n \in \Bbb Z$, determine $\gcd(3n^2 + 7n + 4, n + 2)$.

I factored $3n^2+7n+4$ to $(3n+4)(n+1)$ and because there isn't a common factor of those and $n+2$ I said that the gcd is $1$, but is there any othere way to go about it that would come up with a gcd ...
-1
votes
4answers
50 views

Find the last digit of $\binom{2016}{21}$

Find the last digit of the binomial coefficient: $$\binom{2016}{21}$$ I would start by factorial form: $$\binom{2016}{21} = \frac{2016!}{21!(1995!)}$$ But that doesnt help much?
2
votes
1answer
42 views

Prove that $2$ is irreducible in $\mathbb{Z}[\sqrt{n}]$ if $n$ has a prime factor congruent to $5$ modulo $8$.

Prove that $2$ is irreducible in $\mathbb{Z}[\sqrt{n}]$ if $n$ has a prime factor congruent to $5$ modulo $8$. I know that if $x^2 \equiv \pm2 \pmod p$, where $p$ is a prime, has no solution if ...
15
votes
2answers
100 views

For $N\in \mathbb{N}$, do there exist natural numbers $N<n_1<n_2<\cdots<n_k$ such that $\frac{1}{n_1}+\cdots+\frac{1}{n_k}=1$?

$N$ is a natural number. Is there any $k$ and some natural numbers $N<n_1<n_2<\cdots<n_k$ such that $$\frac{1}{n_1}+\frac{1}{n_2}+\cdots+\frac{1}{n_k}=1$$?
6
votes
4answers
80 views

Prove that if $p$ is a prime such that $p^2+2$ is a prime then $p=3$.

My problem in my solution is that I don't know if the operations I apply on congruence modulo n are admissible. I could really use some guiding: Attempt: Let there be $p\ne 3$ fulfilling the ...
4
votes
3answers
63 views

Prove that ${x^2+y^2=z^n}$ has a solution in $\mathbb{N}$ for all $n$ in $\mathbb{N}$

I am solving it by stating that $$x^2 +y^2 =c^2$$ represents a circle. And when $$c^2=z^n$$ then , it represents a system of concentric circles with radius varying as $z$ varies or $n$ varies. So, for ...
1
vote
0answers
27 views

$\sum_{n=i}^{j}\frac{1}{n}$ Isn't Integer Without Bertrand's Postulate [duplicate]

$i,j\in \mathbb{N}$ and $i<j $. Prove that $$\sum_{n=i}^{j}\frac{1}{n}$$ isn't integer using without using the Bertrand's postulate.
2
votes
1answer
18 views

Invariance Principle Question

A circle is divided into six sectors. Then the numbers $1, 0, 1, 0, 0, 0$ are written into the sectors (counter-clockwise say). You may increase two neighboring numbers by $1$. Is it possible to ...
14
votes
3answers
922 views

A fun problem by Arnold using the Poincaré recurrence theorem

I came across this problem by V. I. Arnold while studying his classical mechanics book. Consider a sequence where the $n^{th}$ term is made up by considering the first digit of $2^n$, the first ...
2
votes
1answer
57 views

Using Fermats prime numbers to prove that there is infinitely many prime numbers

A Fermat number $F_n$ is of the form $F_n = 2^{2^n} + 1$ Furthermore, $F_n = 2 + F_0F_1F_2......F_{n-1}$ Now I already proved that if $n \neq m$ then $\gcd(F_n,F_m) = 1$ Here is the proof Without ...