0
votes
1answer
32 views

Find the number of positive integer $a \leq n$ such that $(a,n) = (a+1,n) = 1)

For every positive integer $n$, let $$A_n = \{a \in \mathbb{N} \mid 1 \leq a \leq n \mid gcd(a,n) = gcd(a+1, n) = 1\}$$ Evaluate $\mid A_n\mid$ Assume that $n$ has the factorization ...
-1
votes
0answers
38 views

How does this method work? [on hold]

Let $n=16$ for an example: step 1: get set of prims from $1$ to $\sqrt{2n}: \{2, 3, 5\}$, step 2: get set of $n \mod 2, n \mod 3, n \mod 5: \{0, 1, 1\}$, setp 3: from $0$ to $n-3$, ...
0
votes
1answer
185 views

Why elements of the set can be Goldbach pairs for a given even number?

Let's take even number $100$ as an example (an example in the paper): Fom $2$ to $\sqrt{100}$ there's four primes:$\ 2,\ 3,\ 5,\ 7.\ $Let $$ \begin{align*} &A=\{n: n \in \mathbb{Z^+}, ...
0
votes
1answer
22 views

Multiplicative functions and Chinese remainder theorem

$ p $ is a nonconstant polynomial with integer coefficients.Define the function $\chi_p(n)$ as the number of zeros of $ p $ in $\mathbb{Z}_n$ for $ n > 1 $, and $ \chi_p(1) = 1 $. e.g., consider $ ...
2
votes
0answers
81 views

Questions about central polygonal numbers $1, 2, 4, 7, 11, 16, 22, 29, 37, 46,\cdots$

Formula for Central polygonal numbers is $\frac{n(n+1)}{2} + 1$, if $n=1$ or $n$ is prime, we get the new sequence $A$: 2, 4, 7, 16, 29, 67, 92, 154, 191, ... It seems that all primes either is ...
1
vote
1answer
44 views

Proof for Carmichael theorem

if $n=p_1^{a_1}p_2^{a_2}p_3^{a_3}\dots p_r^{a_r}$ and $\lambda(n) = lcm[(p_1-1)(p_1^{a_1-1}),(p_2-1)(p_2^{a_2-1}),(p_3-1)(p_3^{a_3-1}),\dots,(p_r-1)(p_r^{a_r-1})]$ then $k^{\lambda{n}} \equiv ...
0
votes
2answers
38 views

Dirichlet Characters and Chineese remainder theorem

Let $k=k_1 k_2$ s.t. $(k_1,k_2)=1$ and let $\chi$ be a dirichlet character mod $k$. I'm trying to prove that there exsists $\chi_1,\chi_2$ dirichlet characters mod $k_1,k_2$ respectively, s.t. ...
4
votes
0answers
21 views

Artin-Schreier Question from Corps Locaux

I have a question from Serre's book "Corps Locaux", namely question 5a in section 2 of chapter IV. It is as follows: "Let $e_K$ be the absolute ramification index of K, and let n be a positive ...
0
votes
0answers
40 views

the non-zero integer roots of an inequality

Let $a,b,c,d$ be real numbers, and $ad-bc \ne 0$, given $$|(ax+by)(cx+dy)|\le \frac{1}{2}|ad-bc|.$$ does there exist non-zero integers $x,y$ which satisfy the above inequality ?
2
votes
2answers
43 views

Find the value of the following Legendre Symbols and Use Gausslemma to compute each of the Legendre symbols below [closed]

Find the value of the following Legendre Symbols: $$a) (18/43)$$ $$b) (19/23)$$ Use Gausslemma to compute each of the Legendre symbols below $$a) (8/11)$$ $$b) (6/31)$$
2
votes
3answers
156 views

Find positive integers $(x,n)$ such that $x^{n} + 2^{n} + 1$ is a divisor of $x^{n+1} +2^{n+1} +1$

Find all positive integers $(x,n)$ such that $x^{n} + 2^{n} + 1$ is a divisor of $x^{n+1} +2^{n+1} +1$ I encountered this question in one of my monthly assignments. Unfortunately, I don't know ...
6
votes
3answers
129 views

Primes as a difference of powers

Find the smallest prime that cannot be written as $$|3^a - 2^b|$$ EDIT: I forgot to mention that $a$ and $b$ are whole numbers. I tried to expand $3^a$ as $(2+1)^a$ using binomial theorem but ...
6
votes
2answers
214 views

A problem based on pigeonhole

Numbers 1 to 1994 are divided into 6 sets.Show that at least in one group there will be two numbers whose sum is also in that group ? We can prove that at least one group will contain more than 332 ...
1
vote
1answer
40 views

Prime triplets and congruences

Show that if $n$, $n+2$ and $n+6$ are a prime triplet then $4320(4((n-1)!+1)+n)+361n(n+2)\equiv0\ \pmod{ (n(n+2)(n+6)}.$
6
votes
1answer
104 views

Every prime power $p^k$ that divides $\binom{2m}{m}$ is smaller than or equal to $2m$

I want to show that every prime power $p^k$ that divides $\binom{2m}{m}$ is smaller than or equal to $2m$. As a first step, I looked at $$\binom{2m}{m} = \frac{(2m)!}{(m!)^2} = \frac{2m(2m-1) \ldots ...
1
vote
0answers
86 views

What is wrong with my argument?

Euler's criterion says (assuming $p$ is a prime and $n$ not a multiple of $p$): 1. $n^{\frac{p-1}{2}} \equiv 1$ (mod $p$), if there is an integer $x$ such that $x^2\equiv n$ (mod $p$) 2. ...
2
votes
1answer
198 views

How to show that the $x^a \equiv 1 \pmod p$ has exactly $\gcd(a,p-1)$ solutions at $Z^*_{p}$?

It is given that $p$ is prime number and $a\ge1$ solution so far: $x^{\gcd(a,p-1)} ā‰” 1$ because it known that a group of units of $Z/pZ$ is cyclic and of order $n=p-1$ for $p$ prime, and also in ...
0
votes
2answers
51 views

integer solution to an equation - do solutions exist?

prove or find a counterexample: The equation $x^n + y^n = z^n$, where $n$ is a natural number, has no solutions at all where $x, y,z$ are integer. counterexample: if $n=3$ and $x=1$ and $y=2$ and ...
3
votes
2answers
83 views

Proof of $ \phi(n) = \sum_{n|d} \mu(d) \cdot\frac nd $

I'd like to prove $\phi(m)=\sum_{m|d}\mu(d)\cdot\frac md$. If I'm right then we have for euler-phi $\phi(n) = \sum_{m \leq n,\gcd(m,n)=1} 1$ Which means: as long as $m$ is less or equal than $n$ ...
0
votes
1answer
31 views

Number Theory Divisibility Question

(From Math Challenge II Number Theory packet) Given that $a,b,n$ are positive integers. Assume that for any positive integer $k\neq b, (k-b)\mid(k^n-a)$, the which of the following must be true? ...
1
vote
1answer
54 views

Why does this equation work?

let $ P(x) := \sum_{p \leq x} Log [p]$, then we have $P(2^{k+1}) = \sum_{i=0}^k ( P(2^{i+1}) - P(2^i)) < 2 \cdot Log[2] \cdot (1 + 2 + 4 +... + 2^k) \leq 4 \cdot Log[2] \cdot 2^k$. Why does ...
4
votes
1answer
87 views

Euler's Refutation of Fermat's Conjecture

Fermat postulated that all numbers of the form $$2^{2^n}+1$$ are prime (where n = any integer). Then Euler came along with a rather ingenious proof that this was not, in fact the case. I came across ...
2
votes
2answers
118 views

When is the power of a binomial equal to the sum of like powers of its terms?

Question: Under what circumstances/restrictions on $x$ and $y$ does $(x + y)^n = x^n + y^n$ given the value of $n$? That is, what can we tell about $x$ and $y$ from the value of $n$ and the equation ...
0
votes
1answer
34 views

Is 2(2k-1) is a perfect square for positive integer k?

For positive integer $k$, let $M = 2(2k-1)$, which of the following must be true? (a) $M$ is not a perfect square for any $k$. (b) There are infinitely many $k$ such that $M$ is a perfect square. ...
2
votes
1answer
44 views

$2^n+1 =xy \implies (2^a|(x-1) \iff 2^a|(y-1))$

I'd like my proof to be verified of the following exercise from Niven's The Theory of Numbers. Section 1.1 Problem 52: Suppose $2^n+1=xy$, where $x$ and $y$ are integers $>1$ and $n>0$. Show ...
1
vote
0answers
47 views

Proof: There are infinite prime numbers of the form 4k+3 [duplicate]

I have to proof if true or wrong: There are infinite prime numbers of the form 4k+3. I want to proof: Yes, this is true. My ideas: 1) Assume - as a contradiction - that there are only infinite prime ...
2
votes
0answers
72 views

How to prove sum of two numbers of the two following forms can be equals to sum of two numbers not of the forms?

The two forms are: $\ 3x^2 + (6y-3)x - y\ $ $\ 3x^2 + (6y-3)x + y - 1, \ \ x,y \in \mathbb{Z}^{+}$ For example: $\ \ \ 5 = \ 3*1^2 + (6*1-3)*1 - 1\ $ ,when $\ x = y = 1\ $,of the two forms $\ ...
2
votes
1answer
34 views

Diophantine Equations problem 2

Find all the solutions to the Diophantine equation x^2+y^2=2(z^2) .I do not have alot of expirience on Diophantine equations and i do not know how to approximate them.I can see that the tripples of ...
0
votes
1answer
49 views

Diophantine equation exercise [duplicate]

Prove that the diophantine equation $x^4-2(y^2)=1$ has only 2 solutions. Any hint on how to start and what to do .. I do not have a lot of experience on non linear diophantine equations and do not ...
1
vote
2answers
40 views

Power of prime number in $n!$ - prove this formula

How to prove: for $ l := \max\{i \in \mathbb{N}_0 : p^i \mid n!\} $ it holds: a) $l = \sum_{i=1}^\infty [\frac{n}{p^i}]$ b) $l \leq [ \frac{n}{p-1} ]$ ? If I take a closer look at the sum in a) I ...
2
votes
1answer
68 views

Find all integers n such that nāˆ’2014 and n+ 2014 are both triangular numbers.

I came across this problem when searching for triangular numbers questions. I know that I need to use the equation, $$\frac {n(n+1)}{2} $$ but I don't know how to apply it to this problem.
0
votes
2answers
48 views

GCD and LCM Problem

Let $x$ and $y$ be positive integers, $x < y$, and $x + y = 667$. Find all pairs $(x,y)$ if $\text{lcm}\,(x,y)/\gcd\,(x,y) = 120$. This problem was from my number theory homework, and I don't get ...
2
votes
1answer
61 views

Prove that if $\gcd(a, n)=1$, then $n\mid a^k-1$ for some $k$

How can I show that if $a$ and $n$ are natural numbers with the condition that $\gcd(a,n)=1$, then there exists a natural number $k$ such that $n \mid a^{k}-1$ What I tried doing is set it up in mod ...
1
vote
3answers
50 views

About the calculation of decimal digits of series up to the nth digit

Considering that we don't know any of the digits of some number defined as the limit up to infinity of a sum, I want to know how many terms do I have to sum to get the correct decimal representation, ...
0
votes
1answer
73 views

prove of $17^n-12^n-24^n+19^n \equiv 0 \pmod{35} $ [duplicate]

i came across this answer and i saw the given solution but i can not understand how it proves the given problem. Ok i get that $lcm(5,7)= 35$ and it is the same as the $(mod 35)$. Please can someone ...
0
votes
3answers
31 views

Modular equations, find x

Problem: Find an integer $x$ such that $x = 5\pmod 8, x = 3 \pmod 9, x = 4 \pmod 7$. Attempt: By the Chinese Remainder Theorem " Suppose $a_1,a_2,...a_k$ are integers pairwise relatively prime ...
0
votes
1answer
111 views

What is a non Trivial Square Root?

I need to understand the concept behind a non trivial square root. Also how to answer these two questions and how to get to the answer? Give a non-trivial square root of 30 Give a non-trivial ...
0
votes
1answer
69 views

How to find the smallest prime divisors of $2^{19}-1$ and $2^{37}-1$?

How to find the smallest prime divisors of $2^{19}-1$ and $2^{37}-1$ ? I'm new to elementary number theory and I'm not sure what to do AT ALL. We're currently studying primitive roots and indices.
1
vote
1answer
47 views

Show a Particular Set of Sentences can be Represented with a WFF

Problem Let $A^{*}_{S}$ be the set of sentences consisting of S1, S2, and all sentences of the form $\phi (0)\rightarrow\forall v_{1}(\phi (v_{1}\rightarrow\phi(Sv_{1}))\rightarrow\forall v_{1}\phi ...
1
vote
1answer
86 views

What are some of the more efficient ways of studying for an Olympiad?

This September I am participating in a competition called the Australian Intermediate Mathematics olympiad, and you may not have heard of it but it's very similar to the AIME. Could you please tell me ...
0
votes
2answers
95 views

Prove $x$ and $y$ in $y = x^2 + 2$ are prime only for $x = 3$ and $y = 11$?

Let $x$ be a positive integer and $y = x^2 + 2$. Can $x$ and $y$ be both prime? The answer is yes, since for $x = 3$ we get $y = 11$, and both numbers are prime. Prove that this is the only value of x ...
1
vote
4answers
65 views

If p is a prime number of the form $4n+3$, show that we cannot solve $x^2\equiv -1\mod p$

Hint: Use Fermat's Theorem that $a^{p-1}\equiv 1\mod p$ if $p \nmid a$. (I have no idea, but something in group theory should help)
2
votes
3answers
66 views

5 digit number $a6a41$ divisible by 9

In the 5-digit number $a6a41$ each of the a's represent the same number. If the number is divisible by 9, what is the digit represented by $a$? I first approached this by saying $$2a + 11$$ since ...
0
votes
1answer
30 views

Number theory question maximum possible difference between $a$ and $b$

$1287a 45b$ is a 8-Digit number, where $a$ and $b$ are not zero. The number is divisible by 18. What is the maximum possible difference between $a$ and $b$? My solution: I first said since it's ...
0
votes
1answer
43 views

Find the natural numbers so that n=2*a^2 ,n=3*b^3 ,n=5*c^5.Number theory problem.

Well here it is i spend almost 3 hours on this one!! Find the general form of the natural numbers that are twice a square ,tripple of a cube and 5 times a 5-ith power.Who is the smaller of them?.What ...
0
votes
0answers
14 views

Group of numbers with common euler's totient function result [duplicate]

I was asked to find the group of integers, which share the result of euler's function of 84. To be clear: which numbers, when applying eulers function on them, result 84. By calculating I found that ...
0
votes
1answer
33 views

Exponential generating function for number of 10 length sequences built from the alphabet, with some restrictions

I've got the following homework question. If anybody could possibly point me in the right direction, that would be great: Suppose X is a sequence with 10 terms built from 26 letters {a, b, c, ..., ...
0
votes
3answers
41 views

Number Theory Remainder Question

I'm trying to find the answer to the following: What is the remainder when 9^2012 is divided by 11? Apparently, you're supposed to use Fermat's Little Theorem, but I'm not sure how to use it to solve ...
1
vote
8answers
159 views

Calculate the last digit of $3^{347}$

I think i know how to solve it but is that the best way? Is there a better way (using number theory). What i do is: knowing that 1st power last digit: 3 2nd power last digit: 9 3rd power last digit: ...
1
vote
4answers
104 views

If $d=\gcd(a+b,a^2+b^2)$, with $\gcd(a,b)=1$, then $d=1$ or $2$

Suppose $\gcd(a,b)=1$. Let $d=\gcd(a+b,a^2+b^2)$. I want to prove that $d$ equals $1$ or $2$. I get that $d\mid2ab$ but I can't find a linear combination that will give me some help to use the fact ...