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

learn more… | top users | synonyms

1
vote
0answers
22 views

Finding Mod Value [duplicate]

I have a problem in finding the solution of the equation given in the form of:$$153^{197}=x \mod 497$$ Can anyone hep me to solve this question?
1
vote
1answer
17 views

Why does the extended euclidean algorithm allow you to find modular inverse?

Why is it that by working backwards from the euclidean algorithm one can find the modular inverse of a number? Further, there is also another method for finding inverses discussed here which seems ...
-1
votes
0answers
10 views

What are the applications of quadratic residues?

I have covered the proofs of the laws of quadratic reciprocity (the Legendre and Jacobi symbols). However this treatment of quadratic residues has been pretty dry. Are there any real life applications ...
1
vote
0answers
23 views

About primes and counting them. [on hold]

Are there bounds to the prime counting function that do not involve logarithms?
5
votes
0answers
25 views

Problems that are made easy by using p-adic numbers

Does anybody know of elementary problems that can be be solved using the p-adics? Solutions are preferred.
4
votes
4answers
321 views

Is the reasoning/algebra for my proof correct? (musical tuning theory proof)

This isn't for a class, I was just wondering if I would be able to work out a proof for something like this myself for fun, and wanted to verify that my methods are correct. Basically, what I'm trying ...
1
vote
1answer
34 views

Integer solutions of the equation $a^{n+1}-(a+1)^n = 2001 $

I am doing number theory and I came across that question $a^{n+1}-(a+1)^n = 2001 $. Find the integer solutions and show that they are the only solution. I really tried hard but i am nowhere near ...
5
votes
1answer
71 views

For $n\ge4$, prove that $1!+2!+\cdots+n!$ cannot be the square of a positive integer

I'm trying to prove this by induction but seem to be getting nowhere.
5
votes
1answer
75 views

$a^3+3a^2+a$ is never a perfect square.

Prove that no number of the form $ a^3+3a^2+a $, for a positive integer $a$, is a perfect square. This problem was published in the Italian national competition (Cesenatico 1991). I've been ...
1
vote
1answer
24 views

Proof on Divisibility of Binomial Coefficients

Prove that $\exists \ i$ $(0 \lt i \lt n)$ such that $$ n \nmid {n \choose i} $$ $\forall \ n$ such that $n \gt 0$ and $n$ is a composite Number.
1
vote
0answers
27 views

Existence of a map $\phi:\mathbb{Z}_{N^2}^* \mapsto \mathbb{F} $

Is there a map between the group of $\mathbb{Z}_{N^2}^*$ where $N$ is a composite number , a product of two equal size secure prime numbers $p$ and $q$ and a finite field $\mathbb{F}$, such that for ...
0
votes
1answer
31 views

Word problem number theory

The number of the students of one school is a natural number that is between $600$ and $500$. If we were to divide the students into $20$ groups or $12$ groups or $36$ groups, we get a remainder of ...
1
vote
3answers
60 views

Find the remainder of $40^{314}$ divided by 91.

Here's what I have so far. $$x \equiv 40^{314} \mod{91}$$ $$\Rightarrow$$ $$x \equiv 40^{314} \mod{7}$$ $$ x \equiv 40^{314} \mod{13}$$ Then by FLT, $$40^6 ≡ 1 \mod{7}$$ $$40^{12} ≡ 1 \mod{13}$$ ...
0
votes
0answers
15 views

Like Carmichael numbers

Given a positive integer $n$ which has a property : $A^n-A$ is divisible by $n$ for all $A\in$ {$2015,2016,2017,...,2014^2-1,2014^2$} . Show that $GCD(k^n-k,n)>1$ for all $k\in ...
0
votes
1answer
11 views

Optimal strategy in Euclid's game

Euclid's game (also known as the Game of Euclid) is played as follows: the players begin with two piles of a and b stones. The players take turns removing m multiples of the smaller pile from ...
1
vote
1answer
36 views

Concerning squarefree numbers with 2 primes and squarefrees with 3 primes.

If a squarefree with two primes is a 2-prime and a squarefree with three primes is a 3-prime is there an integer N such that the number of 2-primes less than N is equal to the number of 3-primes less ...
0
votes
1answer
19 views

Let $m=p^t$ where p is a prime. Prove that $a^{\phi(m)+t} \equiv a^t \bmod{m}$ for ${\bf all}$ integers a

So, I was thinking that $a^{\phi(m)}\equiv 1 \bmod{m}$, thus when multiplying $a^t$ on both sides, we get that $a^{\phi(m)+t} \equiv a^t \bmod{m}$. What is throwing me off is the all integers a part.
3
votes
1answer
35 views

$4|(p-1) \implies$ there is an element $x$ of order $ 4$ modulo $p$.?

"$p \equiv 1 \mod 4 \implies 4 \mid (p-1) \implies$ there is an element $x$ of order $4$ modulo $p$." I am having a difficult time understanding why this implies there is an element $x$ of order $4$. ...
0
votes
0answers
30 views

Summatory Function $F(n) = 1 $ for all $n$ odd, and $F(n) = 2$ for all n even

So, I have this summatory function $$ F(n)=\sum_{d\mid n}f(n)$$ that goes $F(n) = 1$ for $2\nmid n$, and $F(n)=2$ for $2\mid n$. This summatory function is multiplicative. I need to describe the ...
3
votes
4answers
77 views

Prove that $a^7-a$ is divisible by 168 when a is odd

so I saw a similar question that proves $168\mid(a^6-1)$ when $(42,a) = 1$. But for this problem I was not given that gcd$(a,42)=1$. When I factor out a I get $168\mid a\cdot(a^6 - 1)$ and since $a$ ...
0
votes
1answer
15 views

Prove that if d = gcd(m,n) then $\phi(mn)=\phi(m)*\phi(n)/d$ [duplicate]

So if m and n are relatively prime, then the $\phi(mn)=\phi(m)*\phi(n)$ but what happens when $d > 1$?
3
votes
4answers
26 views

Least positive residue of $10! mod 143$

So I got that $10! \equiv 10\ (\textrm{mod}\ 11)$ and $10! \equiv 9\ (\textrm{mod}\ 13)$ but I am not sure how to apply the chinese remainder theorem to arrive at the solution for $x \equiv 10!\ ...
0
votes
0answers
23 views

In $Z/3Z[x]$ find the GCD of $x^5+2x^3+x^2+x+1$ and $x^4+2x^3+x+1$

I know that to do this, I use Euclid's algorithm. So in my first step, I got the following: $x^5+2x^3+x^2+x+1=(x^4+2x^3+x+1)(x+1)+(2x)$. So in the next step, I divide $(x^4+2x^3+x+1)$ by the remainder ...
1
vote
1answer
28 views

Prove that 3 is a primitive root of $7^k$ for all $k \ge 1$

so I am trying to find out how to prove that 3 is a primitive root of $7^k$ for all $k \ge 1$. I am trying to prove this via induction. Thanks.
1
vote
1answer
41 views

Show that $\sigma(n)$ = 5 has no solution

If we define $\sigma(n)$ as the sum of all positive divisors of $n$, is the fact that $\sigma(n)$ = 5 has no solution related to the fact that there is no number $y$ such that $2^y$ = 5?
1
vote
2answers
44 views

Olympic problem on irreducible fraction

Prove that the fraction $\frac{21n+4}{14n+3}$ is irreducible for every natural number $n$.
1
vote
2answers
35 views

Find the largest $d \in \mathbb{N}$ such that for any $x \in \mathbb{N}$ the equation $16^x+10x-1 \equiv 0 \pmod d$

I interpret this problem as being finding the $gcd$ of the set of numbers generated by that given sequence. Checking by hand for a possible pattern in the sequence, I noticed instead that every term ...
-4
votes
0answers
39 views

Which of the following is correct? [on hold]

Let $$X = \frac{1}{1001} + \frac{1}{1002} + \frac{1}{1003} + \cdots + \frac{1}{3001}$$ Then find the correct option. (A) $X < 1$ (B) $X > \frac{3}{2}$ (C) $1 < X < \frac{3}{2}$ (D) ...
3
votes
2answers
73 views

My professor says that this equation in a finite field has a solution but I don't think it does.

More than likely it is I who is mistaken, but is there a chance that my professor made a mistake in the following problem? We are tasked with: Let $p = 3$. We do not have an element of order $5$ in ...
0
votes
2answers
48 views

summation of ceil and floor function

I need a closed solution or a faster algorithm for calculating $$ \sum_{k=1}^{n-1} \left\lceil \frac{n}{k}-1 \right\rceil $$ and $$ \sum_{k=1}^{n-1} \left\lfloor \frac{n}{k} \right\rfloor $$ where $ ...
2
votes
2answers
75 views

For any positive integers $a$ and $b$, the number $(36a+b)(a+36b)$ can never be a power of $2$.

APMO 1998: Show that for any positive integers $a$ and $b$, the number $(36a+b)(a+36b)$ can never be a power of $2$. The solution I've read substitutes $a=2^Ap,b=2^Bq$ where $p$ and $q$ are ...
1
vote
2answers
34 views

Problem about proving fermat's little theorem

We know that, there is an important step to prove Fermat's little theorem, two side times $(n- 1)! \cdot a^{n-1} = (a\cdot1)\cdot(a\cdot2)\cdot...\cdot(a\cdot(n-1)) \equiv (n-1)! \mod(n) $ Example: ...
3
votes
6answers
72 views

Proving $\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$

How would you go about proving that $$\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$$ for any two integers $a$ and $b$? Intuitively it is true because when you divide $a$ and $b$ by ...
0
votes
1answer
29 views

Quadratic congruences problem (x^2-a)(x^2-b)(x^2-ab) ≡ 0 (mod p)

Let p be an odd prime and let a,b ∈ Z such that p ∤ a. Prove that the congruence (x^2-a)(x^2-b)(x^2-ab) ≡ 0 (mod p) is always solvable. Not sure where to begin here.
0
votes
1answer
15 views

Prove that Legendre Symbol ((p-1)!/p) = 1 if p = 1 (mod 4), -1 if p = 3 (mod 4)

Let p be an odd prime. Prove that Legendre Symbol ((p-1)!/p) = 1 if p = 1 (mod 4), -1 if p = 3 (mod 4). Not sure where to begin but here are my initial thoughts. Clearly, the only way p can be an ...
1
vote
3answers
55 views

How to prove $n=\sum_{d\mid n}\phi (d)$

How to prove this equation is true? $$n=\sum_{d\mid n}\phi (d)$$ Where $\phi(d)$ is the Euler's totient function.
4
votes
1answer
79 views

Math Olympiads: GCD of terms in a sequence equals GCD of terms in other sequence

Recently, someone asked for a proof of a problem from the Russian Mathematical Olympiad, 1995. Math Olympiads: GCD of terms in a sequence equals GCD of their indices. The problem was to show that if ...
2
votes
2answers
33 views

What is $(p-1)!$ mod $(1 + 2 + \cdots + (p-1))$ where $p$ is an odd prime? (Exam Q)

I've done a bit of fiddling and I believe the answer to be $(p-1)$ but I don't know how to prove it. The first part of the question asks what $1^p + 2^p + \cdots + (p-1)^p$ is modulo $p$ and it comes ...
4
votes
5answers
85 views

How can I find integers $n \gt 1$ such that the average of $1^2,2^2,3^2…n^2$ is itself a perfect square.

$\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$ so we would like to solve $6k^2=(n+1)(2n+1)$ here we see that $6|(n+1)(2n+1)\implies 2|n+1$ hence we can set $n=2j-1$ $2j(4j-1)=6k^2\implies ...
2
votes
0answers
27 views

How do i prove that $\gcd(a_1,\ldots,a_n)\operatorname{lcm}(a_1,\ldots,a_n)=a_1\cdots a_n$?

Let $a_1,\ldots,a_n$ be nonzero integers. Define $$G=\{A\in\mathbb{Z}:A \text{ is a linear combination of } a_1,\ldots a_n\}$$ My definition for $\gcd(a_1,\ldots,a_n)$ is the principal ideal of $G$. ...
0
votes
0answers
21 views

Finding the largest factor of a number, possible without exhaustion?

Is there a method for determining the greatest factor for a number? Not including itself and without computing all factors(exhaustion).
6
votes
0answers
59 views

infinitely many

It is well known that there are infinitely many positive integers $n$ such that $2^n+1$ is divisible by $n$. Also it is well known that there exist infinitely many positive integers $n$ such that ...
0
votes
0answers
46 views

the proof formula of odd element: $\frac{\Gamma(s)}{\Gamma(1-s)}= \frac{\pi}{\sin(\pi s )}$, $0< s < 1$ [on hold]

$$\frac{\Gamma(s)}{\Gamma(1-s)}= \frac{\pi}{\sin(\pi s )}, \ 0< s < 1.$$ I want to know how to prove the formula without use the Gamma function and Beta function please use series theory to ...
3
votes
3answers
114 views

Which triangular numbers are also squares?

I'm reading Stopple's A Primer of Analytic Number Theory: Exercise 1.1.3: Which triangular numbers are also squares? That is, what conditions on $m$ and $n$ will guarantee that $t_n=s_m$? Show ...
0
votes
1answer
23 views

Real numbers, infinite series and the axiom of choice

I refer here to the question “Can every real number be represented by a (possibly infinite) decimal?” asked by WakeUpDonnie Jun 2 '13 (at 21:43). I have few a follow up questions which are related ...
1
vote
4answers
56 views

Show that if $3\mid(a^2+1)$ then $3$ does not divide $(a+1)$.

Show that if $3\mid(a^2+1)$ then $3$ does not divide $(a+1)$. using proof of contradiction can someone prove this using contradiction method please
5
votes
2answers
132 views

Math Olympiads: GCD of terms in a sequence equals GCD of their indices.

The sequence $a_1 ,a_2 ,a_3 ,...$ of positive integers satisfies $\text{gcd}(a_i ,a_j ) = \text{gcd} (i, j)$ for $i \neq j$. Prove that $a_i = i$ for all $i$. Source: Russian Mathematical Olympiad, ...
1
vote
1answer
35 views

Finding the sixth roots of $-8i$

So to find the sixth roots of $-8i$, it would be equivalent to: $$z^6=-8i$$ So after all the math work, I end up getting my final answer to be: $$\sqrt2 \operatorname{cis}\left(\frac{\theta+2\pi ...
1
vote
0answers
61 views

Is this a property of irrational numbers?

I call this property number solitaire: Numbers that possess the solitaire property can be written in a given base as 0,...1,...2,...3,...,etc, with a decimal point anywhere. For an example look at ...
0
votes
3answers
70 views

Testing If a Three/Four Digit Number is Prime or Not

Thank you for providing such great help. Thanks to math.stack site. I would like to know a good method to test any three/four digit number prime or not? I don't want to go any C or Java or any ...