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

learn more… | top users | synonyms

3
votes
3answers
164 views

Prove for Fibonacci numbers: $3\mid f(n) \iff 4\mid n$

Let $f(n)$ be the $n$th Fibonacci number. Prove that $$3\mid f(n) \iff 4\mid n$$ I tried to use induction to prove it but I couldn't continue when I reached $n+1$ case.
2
votes
3answers
265 views

Prove or disprove an equation about Euler's $\phi$ function

Let $\phi(n)$ be the Euler's phi function and $p>q,m>1$, $\phi(m^p)>\phi(m^q)$ My intuition tells me this is true but I am not sure how to prove it. I know little about Euler's phi ...
4
votes
3answers
209 views

Find the remainder of $1234^{5678}\bmod 13$

Find the reminder of $1234^{5678}\bmod 13$ I have tried to use Euler's Theorem as well as the special case of it - Fermat's little theorem. But neither of them got me anywhere. Is there something ...
3
votes
3answers
157 views

Prove equations in modular arithmetic

Prove or disprove the following statement in modular arithmetic. If $a\equiv b \mod m$, then $ a^2\equiv b^2 \mod m$ If $a\equiv b \mod m$, then $a^2\equiv b^2 \mod m^2$ If $a^2\equiv b^2\mod m^2$, ...
10
votes
4answers
1k views

Prime Partition

A prime partition of a number is a set of primes that sum to the number. For instance, {2 3 7} is a prime partition of $12$ because $2 + 3 + 7 = 12$. In fact, there ...
-1
votes
1answer
182 views

How to prove that $(\frac{n-b}{n}) =(\frac{n}{n})-(\frac{b}{n})$?

How to prove that $\displaystyle\left(\dfrac{n-b}{n}\right) =\left(\dfrac{n}{n}\right)-\left(\dfrac{b}{n}\right) $? What is $\displaystyle\left(\dfrac{n}{n}\right)$? Here, $\left(\dfrac{a}{b}\right)$ ...
0
votes
0answers
100 views

Is this probabilistic argument about “mutual primitive roots” correctly done?

A recent sci.math thread is called "mutual primitive roots". It is about quasi's conjecture that For each prime $q>2$, there is a prime $p<q$ such that $p$ is a primitive root of $q$, and ...
1
vote
2answers
60 views

How to prove $k^n \equiv 1 \pmod {k-1}$ (by induction)?

How to prove $k^n \equiv 1 \pmod {k-1}$ (by induction)?
8
votes
3answers
575 views

Is $n^n$ a perfect square or not?

If $n$ is an integer, how do you know whether $n^n$ is a perfect square, without a calculator? The actual question is: "how many integers between $1$ and $100$ inclusive, raised to their own power, ...
1
vote
3answers
128 views

I don't understand this proof about Gaussian integers

Theorem: If p is a Gaussian prime and $p|zw$ for some gaussian integer $z,w \in Z[i]$ then $p|z$ or $p|w$. Suppose $p \not| z$ and lets deduce $p | w$. Let $u$ be a greatest common divisor of $p, ...
1
vote
1answer
416 views

Infinitely many primes of the form $6\cdot k+1$ , where $k$ is an odd number?

How to prove that there are infinitely many primes of the form $6k+1$ , where $k$ is an odd number ? Here is a proof that there are infinitely many primes of the form $6k+1$ : We will assume that ...
3
votes
2answers
163 views

Proof that the relation $5 \mid (a + 4b)$ is symmetric and transitive

Take the relation $R$ to be defined on the set of integers: $$aRb \iff 5 \mid (a + 4b)$$ As part of a larger proof, I have to show that $R$ is both symmetric and transitive. I'm lost. I see the ...
2
votes
2answers
135 views

Is this proof correct?

The problem is "Can you find a value $n$ such that $n^2+1$ is divisible by $3$?" My analysis: For the divisibility of $n^2+1$ by $3$, we need $n^2 \equiv 2 \pmod{3}$ in other words we need to show ...
14
votes
2answers
1k views

Asking 2011 Putnam B6

I wish to ask today's Putnam problem B6: Suppose $p$ is an odd prime. Prove that for $n\in \{0,1,2...p-1\}$, at least $\frac{p+1}{2}$ number of $\sum^{p-1}_{k=0} k! n^{k}$ is not divisble by $p$. ...
4
votes
4answers
192 views

What are some “natural” interpolations of the sequence $\small 0,1,1+2a,1+2a+3a^2,1+2a+3a^2+4a^3,\ldots $?

(This is a spin-off of a recent question here) In fiddling with the answer to that question I came to the set of sequences $\qquad \small \begin{array} {llll} ...
5
votes
9answers
372 views

Which is the greatest possible natural number that divides $(p+3)(p-7)$, where $p$ is a prime number greater than $3$?

Which is the greatest possible natural number that definitely divides $(p+3)(p-7)$, where $p$ is a prime number greater than $3$? This one is from my module, comes as a fill in the blanks with ...
2
votes
2answers
95 views

If $x^2 \equiv a \pmod n$, then $x^2 \equiv a \pmod {p_i}$, where $n=p_1^{t_1} \dots p_r^{t_r} $: why?

Now I'm not sure why the following holds: If $x^2 \equiv a \pmod n$ for some $x \in \mathbb Z$, then $x^2 \equiv a \pmod {p_i}$ for all $i$, where $n=p_1^{t_1} \dots p_r^{t_r}$. I know that if ...
3
votes
3answers
152 views

How to prove :If $p$ is prime greater than $3$ and $\gcd(a,24\cdot p)=1$ then $a^{p-1} \equiv 1 \pmod {24\cdot p}$?

I want to prove following statement : If $p$ is a prime number greater than $3$ and $\gcd(a,24\cdot p)=1$ then : $a^{p-1} \equiv 1 \pmod {24\cdot p}$ Here is my attempt : The Euler's ...
1
vote
1answer
65 views

How do you get Jacobi symbol $[\frac{3}{8}]$?

How do you get $[\frac{3}{8}]$? Answer is -1, but how do you get that?
3
votes
0answers
186 views

Number of integral solutions

Given a prime number $p$, find the number of pairs of integers $(a, b)$ such that $p \lt a$, $p \lt b$ and $ab$ is divisible by $(a-p)(b-p)$.
1
vote
4answers
189 views

Understanding the $\equiv$ symbol

I am trying to understand a wierd symbol in a book and I am failing. The symbol is this '$\equiv$'. I understood that if I have $32\equiv 2\bmod15$ means that if I divide $32$ with $15$ I will get ...
1
vote
1answer
92 views

Proving $\frac{m-n}{(m+1)(n+1)}=\frac{1}{k}$ for every $k>1$

How can we show that for any integer $k>1$ there are positive integers $m$ and $n$ such that $$\frac{1}{k}=\frac{m-n}{(m+1)(n+1)}.$$ (Thanks to Arthur Fischer for the reformulation!)
1
vote
1answer
93 views

meaning of the notations $\mathbb{Z}^{n}$ and $\# (G/2G)$

Does anybody know what the following means? It was never introduced in the lecture... What is the meaning of $\mathbb{Z}^{n}$? And the meaning of $\#(G/2G)$ where $G$ is a additive group? ...
2
votes
4answers
89 views

How many new digits can appear in a multiplication?

When adding two positive integers, the result is sure to have at most the same number of digits as the largest of the two terms, plus one. What about multiplication? Can many more digits can the ...
1
vote
1answer
232 views

Calculation of prime numbers - why so difficult?

As I read more and more about advanced mathematics, the more complex and obscure topics seem to be tougher to bend the rules of math to describe. However, the simple (and undoubtedly very useful) ...
1
vote
2answers
121 views

Is this proof about Mersenne numbers acceptable?

I want to prove following property of Mersenne numbers : If $p > 3$ then $M_p\equiv 1 \pmod {6\cdot p}$ So, according to Fermat's Little Theorem we may write : $2^p\equiv 2 \pmod p ...
4
votes
2answers
185 views

Coincidences with orders of simple groups

The projective special linear groups $PSL(2,4)$, $PSL(2,5)$ and $PSL(2,9)$ have the property that their orders equal the order of an alternating group. They are also isomorphic to the respective ...
8
votes
3answers
3k views

Find the number of all four-digit positive integers that are divisible by four and are formed by the digits 0,1,2,3,4,5

Find the number of all four-digit positive integers that are divisible by four and are formed by the digits 0,1,2,3,4,5. The combination for all numbers would be $6^4$, but we have a few roadblocks ...
1
vote
1answer
161 views

How to prove this property of Mersenne number factors?

Let us denote a prime factor of Mersenne number as $q$ . How to prove following : $(M_p\equiv0\pmod q \land q\equiv 1 \pmod 8) \Rightarrow q\equiv 1 \pmod {4\cdot p}$ There is a proof that any ...
3
votes
3answers
991 views

Finding the last two digits of $6543^{210}$

I have to find the last two digits of $6543^{210}$, my strategy is to use the Euler theorem and then some algebra to reduce this to $6543^{10}$, however I can't think of any easy way to proceed after ...
4
votes
4answers
865 views

Which is the easiest and the fastest way to find the remainder when $17^{17}$ is divided by $64$?

Which is the easiest and the fastest way to find the remainder when $17^{17}$ is divided by $64$?
3
votes
1answer
379 views

Proving a polynomial $f(x)$ composite for infinitely many $x$

Let $f(x)=a_0+a_1x+ \ldots +a_nx^n$ be a polynomial with integer coefficients, where $a_n>0$ and $n \ge 1$. Prove that $f(x)$ is composite for infinitely many integers $x$. I can easily ...
2
votes
1answer
405 views

Number theory for a high school Calculus student?

I've always loved playing with numbers, but haven't had any formal guidance in the study of advanced mathematics and number theory. Is there a book (or a few books) on mathematics that I wouldn't have ...
10
votes
4answers
5k views

How to use the Extended Euclidean Algorithm manually?

I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?
2
votes
2answers
128 views

how to solve $\pm y \equiv 2x+1 \pmod {13}$ with Chinese remainder theorem or iterative method?

how to solve $\pm y \equiv 2x+1 \pmod {13}$ with Chinese remainder theorem or iterative method? It comes from solving $x^2+x+1 \equiv 0 \pmod {13}$ (* ) and background is following: 13 is prime. ...
0
votes
2answers
313 views

From any given twelve integers, two have a difference that is a multiple of 5

How will you show that from a set of twelve given natural numbers (arbitrary) you can always find two such that their difference is divisible by $5$?
2
votes
3answers
410 views

The last digit of $n^5-n$

What will be the last digit of $$n^5 - n \bmod 1000,$$ where $n$ is a natural number and $m \bmod 1000$ is the remainder when $m$ is divided by $1000$.
10
votes
3answers
979 views

Motivation behind the definition of GCD and LCM

According to me, I can find the GCD of two integers (say $a$ and $b$) by finding all the common factors of them, and then finding the maximum of all these common factors. This also justifies the ...
2
votes
1answer
181 views

Could this $100000004$ digits number be candidate for the record prime number?

Let's observe following number : $ 4517\cdot 2^{332192811}+1$ I have noticed : If $k\cdot 2^{2n+1}+1$ is prime number then $\gcd(k-1,3)=1$ , where $k,n \in Z^{+}$ , so $\gcd(k-1,3)=1$ should ...
2
votes
1answer
329 views

Elementary proof of when -2 is a quadratic residue modulo an odd prime?

Mathworld says that $-2$ is a quadratic residue modulo a prime $p$ if and only if $p=8n+1$ or $p=8n+3$, though I don't understand their explanation. I have seen elementary proofs that $-1$ is a ...
5
votes
4answers
332 views

Are there infinitely many composites of the form $n =2 p_{k_1}p_{k_2} \cdots p_{k_n} + 1$?

Are there infinitely many composites $n$ of the following form $n = 2 p_{k_1} p_{k_2} \cdots p_{k_n} + 1$? In other words are the infinitely many composite numbers constructed using any choices of ...
1
vote
0answers
47 views

Egyptian expansion of $x$ [duplicate]

Possible Duplicate: Prove any rational can be expressed as $\sum\limits_{k=1}^n{\frac{1}{a_k}}$ Let $x$ be a number between $0$ and $1$. Let $a_1$ be the smallest positive integer such ...
1
vote
1answer
99 views

Proof of the BOOK: Bertrand's Postulate, $\prod_{p \leq {2m+1}} p=\left(\prod_{p \leq m+1} p\right)\left(\prod_{{m+1}< p \leq 2m+1} p\right)$

I have a question concerning Bertrand's postulate in "Proofs from the BOOK", on page 8: $$\prod_{p \leq {2m+1}} p=\left(\prod_{p \leq m+1} p \right)\left( \prod_{{m+1} <p \leq 2m+1} p\right)$$ ...
5
votes
2answers
308 views

Nice formula for $\sum\limits_{d|n}(-1)^{n/d}\Phi(d)$?

How do I evaluate $$\sum_{d|n}(-1)^{n/d}\Phi(d)?$$ $\Phi(d)$ is Euler's totient function. Thanks.
2
votes
0answers
367 views

Is this sum equal to the Möbius function?

In the wikipedia page Uses of trigonometry under the section Number theory and in the page for the Möbius function there is an explanation for how to calculate the Möbius function from the GCD=1 ...
1
vote
3answers
107 views

Problem about $[x]$

$$[x]-2[x/2]\leq 1$$ Equivalently, $[x]-2[x/2]$ assumes only the values 0 and 1. It seems easy, but I don't know how to prove it...
9
votes
2answers
241 views

An interesting way of producing positive integers

If we define $$\cal N _1 := \{ 1\} $$ and by induction $$\cal N_{n+1}:=\{x\in \mathbb N | \exists a,b \in\cal N_n : x= a+b \text{ or }x=ab \text{ or }x=a^b \}$$ it's easy to prove that, for every $m ...
1
vote
1answer
91 views

How to show that $p \nmid a \Rightarrow \gcd(p,a)=1$?

How to show that $p \nmid a \Rightarrow \gcd(p,a)=1$? If we have canonical representations of $p= q_1^{b_1} \cdots q_n^{b_n}$ and $a= r_1^{c_1} \cdots r_k^{c_k}$, then because $p \nmid a$, $q_i \neq ...
2
votes
2answers
85 views

Finding a solution of $x^{2}=a \pmod p$

Let $p$ be a prime which is $5 \pmod {8}$. Let $r$ be an element of $\mathbb{Z}/p\mathbb{Z}^*$ of order $4$ and let $a$ be a quadratic residue modulo $p$. Prove that a solution of $x^{2}=a \pmod p$ is ...
1
vote
1answer
294 views

The coin change problem in the quantitative way

Today,I came across this problem: Suppose you have a currency, named miso, in three denominations, $1, 10$ and $50$. In how many ways can $107$ miso be given in this currency if you have ...