Take six coins, candies, almonds, or something or that sort. Arrange them in a $3\times 2$ rectangle. Mix them up and ask your cousin to make them into a rectangle. Then do the same with eight coins and with nine. (9 is important! Otherwise she might think that prime means "odd"!) Do 12 if she hasn't lost interest yet.
(Let's say your cousin never tries arranging the items in a $1\times n$ line. Maybe she naturally won't consider this a rectangle. If she does, the pedagogy will change a little, but the main plan won't.)
Now give her 7 items to arrange in a rectangle. After a while she will discover that they cannot be arranged into a rectangle; there are always some left over.
Then you say:
“Some numbers, like 6 and 8, make rectangles. Others, like 7, don't. A prime number is a number that doesn't make a rectangle.”
If your cousin considers $1\times n$ to be a rectangle, that's all right. After she makes the $1\times 7$ rectangle, say “Yes, that's a special kind of rectangle called a ‘line’. Can every number make a line?” She will agree. “Can 7 items make a rectangle that isn't a line?” Then proceed as before: every number can make a line, and a prime is a number that can only make a line.
I don't know how to get from this to encryption though. If I were talking about encryption, I would omit the primes, which are not the main idea. The important idea is that there are two keys, one for scrambling and one for unscrambling, and you publish the scrambling key and keep the unscrambling one secret. The primes in the RSA and Diffie-Hellman methods are examples of the many ways of accomplishing this, and in fact the first published method of asymmetric encryption did not involve primes, but was based on solutions to the knapsack problem.
If what she really wanted to understand is how anything could be encrypted at all, I would take a completely different path. Show her how to add a secret key to a plaintext, adding each pair of letters mod 26, to get a ciphertext. For example, if the key is YOBGORGLE
and the plaintext is THURSDAY
, the sum is SWWYHVHK
, where for example S
= Y
+ T
because $25+20\equiv 19\pmod{26}$.
Then someone who wants to decrypt the ciphertext and who knows the key can subtract the key from the ciphertext, again mod 26, to get the plaintext again.
Ruling out $n=1$ and $3|n$ we have the following conjecture :
For every natural number $n$, there is a prime with digitsum $n$.
The conjecture is definitely true for $2\le n\le 200$ (I found proven primes with PARI/GP) and very probably true for $2\le n\le 1000$ (The numbers I found passed $10$ strong probable-prime-tests)
Since there are infinite many numbers with digit-sum $n$ for every $n$, and many of these numbers are "small", it is very likely that we find a prime for every $n$.
This should give an overhelming heuristical argument to believe that the claim is true for all $n$.
A proof of this conjecture is very probably currently out of reach.
Best Answer
You might look at OEIS A046704