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

learn more… | top users | synonyms (1)

1
vote
2answers
180 views

calculate $a^{(P-1)/2}\pmod{P}$ for large prime

How can I calculate $a^{(P-1)/2}\pmod{P}$? for example $3^{500001}\bmod{1000003}$ given that $1000003$ is prime. I know that if we square the number $3^{500001}$ the result will be either $1$ or ...
1
vote
2answers
45 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.
1
vote
4answers
80 views

Prove that if $3|mn$, then $3|m$ or $3|n$

I am trying to prove this for integers $m$ and $n$. I tried to reach prove that $3|m$ by assuming that 3 does not divide $n$, but this is such a basic assumption of mine already that it is hard for ...
1
vote
2answers
46 views

analytical ability and logical reasoning

There are $6561$ balls out of which $1$ is heavy. Find the minimum number of times the balls have to be weighed for finding out the heavy ball. How can I solve this step by step?
1
vote
3answers
44 views

Least quadratic nonresidue modulo $p$ is a prime.

Let $p$ be an odd prime. Then, show that the least quadratic nonresidue modulo $p$ is a prime. As a hint is given the fact that Legendre symbol is a homomorphism.
1
vote
2answers
85 views

Find all n such that $\phi(\phi(n)) = 1$

Find all n such that $\phi(\phi(n)) = 1$. I was thinking of firstly writing $\phi(n) = n\prod_{p|n} {1-1/p}$ and then again but I couldn't find a result.
1
vote
3answers
66 views

Proving that every triangular number $\frac{k(k+1)}{2}$ has a remainder of $0$ or $1$ when divided by $3$

I need to show that every triangular number $\frac{k(k+1)}{2}$, where $k$ is a natural number, will have a remainder of either $0$ or $1$ when divided by $3$. I was thinking of either considering the ...
1
vote
2answers
357 views

Find the sum of 101 numbers on a blackboard

Alyssa writes 101 distinct positive integers on a blackboard, in a row, so that the sum of any two consecutive integers is divisible by 5. Let N be the smallest possible sum of all 101 integers. Find ...
1
vote
4answers
93 views

Euclid proof of infinite primes.

http://en.wikipedia.org/wiki/Euclid's_theorem I just read euclids proof for the existence of infinitely many primes (I have never used his proof earlier to prove this). It seems to me that he assumes ...
1
vote
4answers
69 views

Show that if $m^2 + n^2 $ is divisible by $4$, then $mn$ is also divisible by $4$.

Show that if $m$ and $n$ are integers such that $m^2 + n^2 $ is divisible by $4$, then $mn$ is also divisible by $4$. I am not sure where to begin.
1
vote
2answers
165 views

Why don't we use Presburger's arithmetic instead of Peano's arithmetic?

I was reading about quantifier elimination and discovered the Presburger Arithmetic, the article mentions two points about it: It is decidable, complete and consistent. It omits multiplication ...
1
vote
3answers
63 views

a question about relatively prime numbers

Is it true that if $m, n$ are relatively prime integers, then $mn$, $m-n$ are also relatively prime? It seems intuitively true but I can't prove it... Could anyone help me how to prove it?
1
vote
5answers
59 views

Remainder when $p$ is divided by $6$

Let $p$ be a prime. If there is a remainder of $1$ on division of $p$ by $3$, then what is the remainder when $p$ is divided by $6$? why? I know the remainder is $1$ in both the cases, but I'm ...
1
vote
2answers
53 views

How else could we solve the congruence?

How could I solve the congruence $6x \equiv 1 \pmod { 5^4}$? I wanted to use the formula $x_n=\frac{5^4+1}{6}$, but calculating this number, we see that it is not integer. How else could we solve ...
1
vote
5answers
86 views

How did we find the solution?

In my lecture notes, I read that "We know that $$x^2 \equiv 2 \pmod {7^3}$$ has as solution $$x \equiv 108 \pmod {7^3}$$" How did we find this solution? Any help would be appreciated!
1
vote
1answer
59 views

$\sqrt {-6}$ is not prime in $\mathbb{Z}+\mathbb{Z}\sqrt {-6}$

Suppose $\sqrt{-6}|(a+b\sqrt{-6})(c+d\sqrt{-6})$. I need to show that $\sqrt{-6}$ does not divide $(a+b\sqrt{-6})$ and does not divide $(c+d\sqrt{-6})$. I thought you might arrive at some ...
1
vote
1answer
47 views

Is there a composite integer $n \geq 9$ such that $n \nmid (n-1)!$? [duplicate]

Is there a composite integer $n \geq 9$ such that $n \nmid (n-1)!$? If we are not talking about composites then by Wilson's theorem we have $n \nmid (n-1)!$.
1
vote
5answers
268 views

n is even if and only if n leaves remainder 0, 2, 4, 6 or 8 when divided by 10

"Let n be any given positive integer. Prove that n is even if and only if n leaves remainder 0, 2, 4, 6 or 8 when divided by 10". Am I correct in thinking that with regards to the "if and only if" ...
1
vote
3answers
79 views

First index of number in that arithmetic progression which is a multiple of the given prime number

I have a prime number $p$, an arithmetic progression starting at $a$ with common difference $d$. How to find the first index of a term in that arithmetic progression which is a multiple of the given ...
1
vote
3answers
116 views

Number theory proofs regarding gcd's

How would you prove if $ad-bc = 1$, then $(a+c,b+d)=1$
1
vote
2answers
87 views

Better proof that $n \leq 2n$ for all natural numbers?

I tried proving via induction on naturals that $n \leq 2n$ for each natural $n$. Obviously, $0 \leq 2(0)$, and then assuming for any given $n$, $n \leq 2n$, you just show that $n + 1 \leq 2(n + 1).$ ...
1
vote
4answers
2k views

Is it possible to do modulo of a fraction

I am trying to figure out how to take the modulo of a fraction. For example: 1/2 mod 3. When I type it in google calculator I get 1/2. Can anyone explain to me how to do the calculation?
1
vote
4answers
195 views

Number of numbers between a and b and sums from x to y

This is for my benefit and curiosity and not homework. How do you calculate the number of numbers between $1$ and $100$? How do you calculate the number of even and odd numbers between $1$ and $100$? ...
1
vote
2answers
992 views

Given perimeter of triangle and one side, find other two sides

In triangle ABC, all three sides have integer lengths. If AB = 21, the perimeter is 54, and the area is a positive integer, what are the lengths of BC and AC? I tried using Heron's Formula, but I ...
1
vote
2answers
114 views

Does the equation $x^n\equiv 1\pmod p$ has at most $n$ solutions?

Does the equation $x^n\equiv 1\pmod p$, $p$ being a prime has at most $n$ solutions? If it does, how to show it? (I don't know a thing about fields.)
1
vote
3answers
123 views

Verify that $4(29!)+5!$ is divisible by $31$.

Verify that $4(29!)+5!$ is divisible by $31$ I know I have to use Wilsons theorem: $(p-1)!=-1\pmod p$ but I'm not really sure how to apply this theorem. Step by step explanation please? Thank you!
1
vote
2answers
86 views

Probability of number formed from dice rolls being multiple of 8

A fair 6-sided die is tossed 8 times. The sequence of 8 results is recorded to form an 8-digit number. For example if the tosses give {3, 5, 4, 2, 1, 1, 6, 5}, the resultant number is $35421165$. ...
1
vote
4answers
125 views

Is this a true theorem? [closed]

I'm trying to prove the existence of the following theorem: If $n,p \in \mathbb{N}$, then $(p+1)^n = 1 \mod p$ Is this theorem true? I think it is, but I don't know how to prove it! Thanks!
1
vote
3answers
629 views

Find the smallest positive integer x such that 2015! ≡ x (mod 2017)

Q. The next year that is a prime is 2017. Find the smallest positive integer x such that 2015! ≡ x (mod 2017). So, this is what I have; By Wilson’s theorem, (2017-1)! ≡ -1 (mod 2017) ⇒ 2016! ≡ -1 ...
1
vote
2answers
107 views

Integer solutions of $800000007 = x^2+y^2+z^2$

Prove that the equation, $800000007 = x^2+y^2+z^2$ has no solutions in integers.(That is $8$ followed by $7$ zeroes, with a $7$ at the end). I tried checking modulo $3$, $5$, $7$, and $10$, but ...
1
vote
6answers
266 views

Solution of $\dfrac{a}{b}=\dfrac{a'}{b'}$ if $a,b,a',b' \in \mathbb{N}$

Let $\dfrac{a}{b}=\dfrac{a'}{b'}$ , $a,b,a',b' \in \mathbb{N}$ s.t. $a$ and $b$ have no common factors. How can we show that the only solution to this equality is $a'=na$ and $b'=nb$, $n$ is a natural ...
1
vote
3answers
197 views

If $\gcd(a, b) = 1$ and if $ab = x^2$, prove that $a, b$ must also be perfect squares; where $a,b,x$ are in the set of natural numbers

Problem: If $\gcd(a, b) = 1$ and If $ab = x^2$ ,prove that $a$, $b$ must also be perfect squares; where $a$,$b$,$x$ are in the set of natural numbers I've come to the conclusion that $a \ne b$ and ...
1
vote
4answers
240 views

Find the last two digits of 9^(9^9) [duplicate]

I want to find the last two digits of $9^{9^9}$, that is $9$ raised to the power $9^9$. I tried using Euler's theorem but I can't make anything of it. As always, I ask only for a minor hint, not a ...
1
vote
1answer
51 views

Prove that $8.\overline{74}\in\mathbb{Q}$

Prove that $8.\overline{74}\in\mathbb{Q}$ My try :: $8.\overline{74}=a/b\implies b 8.\overline{74}=a$ But in fact i don't know how to prove it, maybe someone will help.
1
vote
3answers
95 views

There exists an integer with alternating digits $1$ and $2$ which is divisible by $2013$

Could someone give me hints in how to solve the following (rather interesting) problem? Prove that there exists an integer consisting of an alternance of $1$s and $2$s with as many $1$s as $2$s ...
1
vote
3answers
82 views

Prove by induction that $3\mid (n^3 - n)$

I'm having an argument with my professor whether my exam was right or not. Before I sign a formal complain to get a review on my exam, I'd like to be sure it's correct. My answer: Proof by induction: ...
1
vote
2answers
166 views

Prime factorization, distinct primes

Let $n=p^eq^f$ where $p$ and $q$ are distinct primes and $e$ and $f$ are positive integers. Show that $n$ has $(e + 1)(f + 1)$ distinct factors in $N$, and that the sum of all these factors is ...
1
vote
3answers
166 views

Integer ordered pairs $(x,y)$ for which $x^2-y!$…

[1] Total no. of Integer ordered pairs $(x,y)$ for which $x^2-y! = 2001$ [2] Total no. of Integer ordered pairs $(x,y)$ for which $x^2-y! = 2013$ My Try:: (1) $x^2-y! = 2001\Rightarrow x^2 = ...
1
vote
3answers
150 views

What is the remainder of dividing $14^{256}$ by $17$?

What is the remainder of dividing $14^{256}$ by $17$? $$14^2\equiv 196\equiv 9 ...
1
vote
2answers
257 views

Representing an Integer as a Sum of at Most $k$ Triangular Numbers

What is the smallest $k$ such that every $n \in \mathbb{N}$ can be represented by a sum of exactly $k$ triangular numbers? For the sake of simplicity, I will assume $0$ is a triangular number. I've ...
1
vote
3answers
131 views

Prove that there are infinitely many perfect cubes of the form $p^2+3q^2$

Prove that there are infinitely many perfect cubes of the form $p^2+3q^2$ where $p$ and $q$ are integers. Hint: one approach is to set $p^2+3q^2=(a^2+3b^2)^3$ and then find $(p,q)$ in terms of $a,b$. ...
1
vote
5answers
298 views

If $x,y$ are integers such that $3x+7y$ is divisible by $11$, then which of the following is divisible by $11$?

I am currently studying for the GRE, and this question came up. Let $x$ and $y$ be positive integers such that $3x+7y$ is divisible by $11$. Which of the following must also be divisible by $11$? ...
1
vote
3answers
142 views

definition of $\mathbb{N}:=\bigcap Ind$

--- let $A$ a set, $A^+=A \cup \{A\}$ --- let $B$ a set, B is inductive if $\emptyset \in B \wedge \forall A \in B(A^+ \in B )$ --- let $Ind:=\{C|C \text{ is inductive }\}$ is correct this ...
1
vote
2answers
187 views

Proof $\frac{1}{2}+\frac{1}{3}+…\frac{1}{n}$ is not an integer for integer $n>1$ [duplicate]

I found a way to prove this using Chebychev's theorem, are there ways to solve it without relying on this?
1
vote
2answers
78 views

Let $p$ be an odd prime, and denote $A_p$ the integer for which $1 + \frac{1}{2} + \cdots + \frac{1}{p-1} = \frac{A_p}{(p-1)!}$. Prove that $p|A_p$

Let $p$ be an odd prime, and denote by $A_p$ the integer for which $$1 + \frac{1}{2} + \cdots + \frac{1}{p-1} = \frac{A_p}{(p-1)!}$$ prove that $p|A_p$.
1
vote
4answers
183 views

Mathematical Induction prime help

I recently obtained "What is Mathematics?" by Richard Courant and I am having trouble understanding what is happening with the Prime Number Unique Factor Composition Proof (found on Page 23). The ...
1
vote
2answers
156 views

Proving x and y is divisible by p (prime).

If p is a prime number and x and y are integers, how do I prove "if xy and x+y are both divisible by p, then x and y is divisible by p"? I started like this.. 1) p divides xy, so p divides x or p ...
1
vote
1answer
85 views

Does $a \mid bc$ imply $\frac{a}{(a,b)} \mid c$?

If $a \mid bc$, then does $\frac{a}{(a,b)} \mid c$? I doubt anybody here is industrious enough to show this via a diagram, but who knows.
1
vote
1answer
67 views

An exercise in Number theory

Let $m$, $n$ and $k$ be positive integers with gcd$(mn, k) = 1$. How can I prove that $x^m + y^n = z^k $has a solution in positive integers?
1
vote
1answer
831 views

Quadratic Congruence (with Chinese Remainder Thm)

How do we solve quadratic congruences such as: $x^2 \equiv11 \pmod{39}$ I know I must use the chinese remainder theorem with $p = 13, 3$ but I've only done linear examples and am unsure about ...